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.

We consider the problem of making apps fault-tolerant through replication, when apps operate at the microsecond scale, as in finance, embedded computing, and microservices apps. These apps need a replication scheme that also operates at the microsecond sca ...

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. ...

We introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to i ...

The atomic commit problem lies at the heart of distributed database systems. The problem consists for a set of processes (database nodes) to agree on whether to commit or abort a transaction (agreement property). The commit decision can only be taken if all processes are initially willing to commit the transaction, and this decision must be taken if all processes are willing to commit and there is no failure (validity property). An atomic commit protocol is said to be non-blocking if every correct process (

Byzantine Agreement (BA) allows 𝑛 processes to propose input values to reach consensus on a common, valid 𝐿 𝑜-bit value, even in the presence of up to 𝑡 < 𝑛 faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomiza ...

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborati ...

The failure detector approach for solving distributed computing problems has been celebrated for its modularity. This approach allows the construction of algorithms using abstract failure detection mechanisms, defined by axiomatic properties, as building b ...

Portability and efficiency are usually antagonists in multi-core computing. In order to develop efficient code, one needs to take into account the topology of the target multi-cores (e.g., for locality). This clearly hampers code portability. In this paper ...

This paper considers the problem of robustly emulating a shared atomic memory over a distributed message passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduc ...

Classic synchronous consensus algorithms are leaderless in that processes exchange proposals, choose the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are typically leader-based. Although t ...

Software transactional memory (STM) is a promising technique for writing concurrent programs. So far, most STM approaches have been experimentally evaluated with small-scale microbenchmarks. In this paper, we present several surprising results from implementing and experimenting with STMBench7 – a large scale benchmark for STMs. First, all STMs we used crashed, at some point or another, when running STMBench7. This was mainly due to memory management limitations. This means that, in practice, none of the te

One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of

n

processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to deci ...

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

We show that, in contrast to the general belief in the distributed computing community, linearizability, the celebrated consistency property, is not always a safety property. More specifically, we give an object for which it is possible to have an infinite history that is not linearizable, even though every finite prefix of the history is linearizable. The object we consider as a counterexample has infinite nondeterminism. We show, however, that if we restrict attention to objects with finite nondeterminism

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations. Namely, our study of quorum systems encompasses, at the same time, the optimal resilience of distributed object implementations (just like traditional quorum

Modern machine learning architectures distinguish servers and workers. Typically, a d-dimensional model is hosted by a server and trained by n workers, using a distributed stochastic gradient descent (SGD) optimization scheme. At each SGD step, the goal is ...

The remote-procedure-call abstraction, including its derivates (underlying, for example, Java RMI, CORBA, and .NET), currently represents one of the most popular paradigms for devising distributed applications. Objects (when acting as servers) are invoked remotely (by clients) through proxies (also called stubs). Because proxies offer the same interfaces as their respective associated remote objects, they hide distribution details, leading to a convenient distributed-programming style that enforces type saf

We present GARFIELD, a library to transparently make machine learning (ML) applications, initially built with popular (but fragile) frameworks, e.g., TensorFlow and PyTorch, Byzantine–resilient. GARFIELD relies on a novel object–oriented design, reducing t ...

Large Language Models (LLMs) have gained significant attention in recent years due to their potential to revolutionize various industries and sectors. However, scaling LLMs further requires access to substantial linguistic resources that are being rapidly ...

We study f -resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our ﬁrst theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f -resilient atomic objects and reliable registers can solve the con

Rachid Guerraoui

Chat with Graph Search

Microsecond Consensus for Microsecond Applications

Crime and Punishment in Distributed Byzantine Decision Tasks

Optimistic Concurrency with OPTIK

How Fast can a Distributed Transaction Commit?

Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

Never Say Never Probabilistic & Temporal Failure Detectors

Abstracting Multi-Core Topologies with MCTOP

The Collective Memory of Amnesic Processes

Leaderless consensus

Dividing Transactional Memories by Zero

Sharing is Harder than Agreeing

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Linearizability Is Not Always a Safety Property

Refined Quorum Systems

AKSEL: Fast Byzantine SGD

Distributed programming with typed events

GARFIELD: System Support for Byzantine Machine Learning (Regular Paper)

Robust and Private Federated Learning on LLMs

The impossibility of boosting distributed service resilience