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.

Decentralized learning is appealing as it enables the scalable usage of large amounts of distributed data and resources (without resorting to any central entity), while promoting privacy since every user minimizes the direct exposure of their data. Yet, wi ...

Gossip-based communication protocols are appealing in large-scale distributed applications such as information dissemination, aggregation, and overlay topology management. This paper factors out a fundamental mechanism at the heart of all these protocols: ...

Informally, an indulgent algorithm is a distributed algorithm that tolerates unreliable failure detection: the algorithm is indulgent towards its failure detector. This paper formally characterizes such algorithms and states some of their interesting features. We show that indulgent algorithms are inherently safe and uniform. We also state impossibility results for indulgent solutions to divergent problems like consensus, and failure-sensitive problems like non-blocking atomic commit and terminating reliabl

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This pape ...

This paper establishes tight bounds on the \emph{best-case} time-complexity of distributed atomic read/write storage implementations that tolerate \emph{worst-case} conditions. We study asynchronous robust implementations where a writer and a set of reader ...

The Paxos part-time parliament protocol of Lamport provides a non trivial but very practical way to implement fault-tolerant deterministic services over a distributed message passing system. This paper deconstructs Paxos and modularly reconstructs more resilient and efficient variants of it, which can furthermore be customised for specific system configurations. The deconstruction consists in factoring out the key algorithmic principles of Paxos within three abstractions: round-based register, round-based c

This paper presents a multicast algorithm for peer-to-peer dissemination of events in a distributed topic-based publish-subscribe system, where processes publish events of certain topics, organized in a hierarchy, and expect events of topics they subscribed to. Our algorithm is ``data-aware'' in the sense that it exploits information about process subscriptions and topic inclusion relationships to build dynamic groups of processes and efficiently manage the flow of information within and between these proce

This paper presents elastic transactions, a variant of the transactional model. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and initiate a new transaction which might ...

Trojan messages are messages that seem correct to the receiver but cannot be generated by any correct sender. Such messages constitute major vulnerability points of a distributed system---they constitute ideal targets for a malicious actor and facilitate f ...

This paper presents the abstraction of lazy consensus and argues for its use as an effective component for building distributed agreement protocols in practical asynchronous systems where processes and links can crash and recover. Lazy consensus looks like consensus, is equivalent to consensus, but is not consensus. The specification of lazy consensus has an on-demand and a re-entrant flavors that makes its use very efficient, especially in terms of forced logs, which are known to be major sources of overhe

This paper defines the fault-tolerant mutual exclusion problem in a message-passing asynchronous system and determines the weakest failure detector to solve the problem. This failure detector, which we call the trusting failure detector, and which we denote by T, is strictly weaker than the perfect failure detector P but strictly stronger than the eventually perfect failure detector P. The paper shows that a majority of correct processes is necessary to solve the problem with T. Moreover, T is also the weak

We show that it is impossible to design a transactional memory system which ensures parallelism, i.e. transactions do not need to synchronize unless they access the same application objects, while ensuring very little consistency, i.e. a consistency condit ...

Transactional memory (TM) is a promising paradigm for concurrent programming. This paper is an overview of our recent work on defining a theory of TM. We first present a correctness condition of a TM, ensured by most existing TM implementations. Then, we d ...

Many fields make use nowadays of machine learning (ML) enhanced applications for cost optimization, scheduling or forecasting, in- cluding the energy sector. However, these very ML algorithms consume a significant amount of energy, sometimes going against ...

This book provides an introduction to distributed programming abstractions and presents the fundamental algorithms that implement them in several distributed en- vironments. The reader is given insight into the important problems of distributed computing and the main algorithmic techniques used to solve these problems. Through examples the reader can learn how these methods can be applied to build- ing distributed applications. The central theme of the book is the tolerance to uncertainty and adversarial in

This article determines the weakest failure detectors to implement shared atomic objects in a distributed system with crash-prone processes. We first determine the weakest failure detector for the basic register object. We then use that to determine the we ...

At the heart of state machine replication, the celebrated technique enabling decentralized and secure universal computation, lies Atomic Broadcast, a fundamental communication primitive that orders, authenticates, and deduplicates messages. This paper pres ...

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, n processes use l different authenticated identifiers, where 1 ≤ l ≤ n. In this paper, we ask how many identifiers are actually needed to reach agreement in a distributed system with t Byzantine processes. We show that having 3t+1 identifiers

This note gives a high level and informal account of the necessary part of the proof that Ω is the weakest failure detector to implement consensus with a majority of correct processes. The proof originally appeared in a widely cited but rarely understood paper by Chandra, Hadzilacos and Toueg. We describe it here as a play in five acts, preceded by a prologue and followed by an epilogue.

Rachid Guerraoui

Chat with Graph Search

The Privacy Power of Correlated Noise in Decentralized Learning

Gossip-Based Peer Sampling

Indulgent Algorithms

The Semantics of Progress in Lock-Based Transactional Memory

Lucky Read/Write Access to Robust Atomic Storage

Deconstructing Paxos

Data-Aware Multicast

Data-Aware Multicast

Elastic Transactions

Finding Trojan Message Vulnerabilities in Distributed Systems

Making Consensus Practical

Mutual Exclusion in Asynchronous Systems with Failure Detectors

The PCL Theorem. Transactions cannot be Parallel, Consistent and Live

The Theory of Transactional Memory

On the advantages of P2P ML on mobile devices

Introduction to Reliable and Secure Distributed Programming

Tight Failure Detection Bounds on Atomic Object Implementations

Chop Chop: Byzantine Atomic Broadcast to the Network Limit

Byzantine agreement with homonyms

The CHT Play