Publications by Rachid Guerraoui

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In concurrent systems without automatic garbage collection, it is challenging to determine when it is safe to reclaim memory, especially for lock-free data structures. Existing concurrent memory reclamation schemes are either fast but do not tolerate process delays, robust to delays but with high overhead, or both robust and fast but narrowly applicable. This paper proposes QSense, a novel concurrent memory reclamation technique. QSense is a hybrid technique with a fast path and a fallback path. In the comm

This paper presents SOAR: the first oblivious atomicity assertion with polynomial complexity. SOAR enables to check atomicity of a single-writer multi-reader register implementation. The basic idea underlying the low overhead induced by SOAR lies in greedi ...

This paper describes a modular approach for the construction of fault-tolerant agreement protocols. The approach is based on a generic consensus service. Fault-tolerant agreement protocols are built using a client-server interaction, where the clients are the processes that must solve the agreement problem, and the servers implement the consensus service. This service is accessed through ``a generic consensus filter'', customized for each specific agreement problem. We illustrate our approach on the constru

Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a co ...

We propose fingerprinting, a new technique that consists in constructing compact, fast-to-compute and privacy-preserving binary representations of datasets. We illustrate the effectiveness of our approach on the emblematic big data problem of K-Nearest-Nei ...

Gossip, also known as epidemic dissemination, is becoming an increasingly popular technique in distributed systems. Yet, it has remained a partially open question: how robust are such protocols? We consider a natural extension of the random phone-call model (introduced by Karp et al. [KarpFOCS-2000]), and we analyze two different notions of robustness: the ability to tolerate adaptive failures, and the ability to tolerate oblivious failures. For adaptive failures, we present a new gossip protocol, TrickleGo

Software Transactional Memory (STM) promises to simplify concurrent programming without requiring speciﬁc hardware support. Yet, STM’s credibility lies on the extent to which it can leverage multi-cores to outperform sequential code. A recent CACM paper [8] questioned however the ability of STMs to provide good performance and suggested their conﬁnement to a research toy. This paper revisits those conclusions through the most to date extensive comparison of STM performance to sequential code. We evaluate a

Gossip, also known as epidemic dissemination, is becoming an in- creasingly popular technique in distributed systems. Yet, it has remained a partially open question: how robust are such protocols? We consider a natural ex- tension of the random phone-call model (introduced by Karp et al.), and we analyze two different notions of robustness: the ability to tolerate adaptive fail- ures, and the ability to tolerate oblivious failures. For adaptive failures, we present a new gossip protocol, TrickleGossip, whic

The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties. In modern variants of such systems, each party is equipped with a security module. The security modules trust each other but can only communicate by exch ...

Replicated systems provide the foundation for most of today’s large-scale services. Engineering such replicated system is an onerous task. The first—and often foremost—step in this task is to establish an appropriate set of design goals, such as availability or performance, which should synthesize all the underlying system properties. Mixing design goals, however, is fraught with dangers, given that many properties are antagonistic and fundamental trade-offs exist among them. Navigating the harsh landscape

This paper establishes tight bounds on the best-case time-complexity of distributed atomic read/write storage implementations that tolerate worst-case conditions. We study asynchronous robust implementations where a writer and a set of reader processes (clients) access an atomic storage implemented over a set of

2t+b+1

server processes of which

t

can fail:

b

of these can be malicious and the rest can fail by crashing. We define a {\em lucky} operation (read or write) as one that runs synchronously and

Byzantine agreement, arguably the most fundamental problem in distributed computing, operates among n processes, out of which t < n can exhibit arbitrary failures. The problem states that all correct (non-faulty) processes must eventually decide (terminati ...

Modern data center fabrics open the possibility of microsecond distributed applications, such as data stores and message queues. A challenging aspect of their development is to ensure that, besides being fast in the common case, these applications react fa ...

This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity and time complexit ...

Large language models (LLMs) have demonstrated remarkable capabilities across various domains but remain susceptible to hallucinations and inconsistencies, limiting their reliability. Retrieval-augmented generation (RAG) mitigates these issues by grounding ...

Memory disaggregation is an emerging data center architecture that improves resource utilization and scalability. Replication is key to ensure the fault tolerance of applications, but replicating shared data in disaggregated memory is hard. We propose SWAR ...

This paper studies the time complexity of reading unauthenticated data from a distributed storage made of a set of failure-prone base objects. More specifically, we consider the abstraction of a robust read/write storage that provides wait-free access to unauthenticated data over a set of base storage objects with

t

possible failures, out of which at most

b

are arbitrary and the rest are simple crash failures. We prove a

2

communication round-trip lower bound for reading from a {\em safe} storage that

An e-Transaction is one that executes exactly-once despite failures. This paper describes a distributed protocol that implements the abstraction of e-Transactionsin three-tier architectures. Three-tier architectures are typically Internet-oriented architectures, where the end-user interacts with front-end clients (e.g., browsers) that invoke middle-tier application servers (e.g., web servers) to access back-end databases. We implement the e-Transaction abstraction using an asynchronous replication scheme th

It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. Th ...

Just like Remote Procedure Call (RPC) turned out to be a very effective OS ab-straction in building client-server applications over LANs, Type-based Publish-Sub-scribe (TPS) can be viewed as a high-level candidate OS abstraction for building Peer-to-Peer (P2P) applications over WANs. This paper relates our preliminary, though positive, experience of implementing and using TPS over JXTA: an analogous to the sockets for P2P infrastructures. We show that, at least for P2P applications with the Java type model,

Rachid Guerraoui

Chat with Graph Search

Fast and Robust Memory Reclamation for Concurrent Data Structures

A scalable and oblivious atomicity assertion

The Generic Consensus Service

Dynamic Byzantine Reliable Broadcast

Fingerprinting Big Data: The Case of KNN Graph Construction

How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)

Why STM can be more than a Research Toy

How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)

Gracefully Degrading Fair Exchange with Security Modules

Trade-offs in Replicated Systems

Lucky Read/Write Access to Robust Atomic Storage

All Byzantine Agreement Problems Are Expensive

uKharon: A Membership Service for Microsecond Applications

Fast Byzantine Agreement

Efficient Federated Search for Retrieval-Augmented Generation

SWARM: Replicating Shared Disaggregated-Memory Data in No Time

How Fast Can a Very Robust Read Be?

Implementing E-transactions with asynchronous replication

The Weakest Failure Detectors to Boost Obstruction-Freedom

OS Support for P2P Programming: a Case for TPS