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.

The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0, 1}, so that b ...

It is now recognized that the Consensus problem is a fundamental problem when one has to design and implement reliable asynchronous distributed systems. This chapter is on the Consensus problem. It studies Consensus in two failure models, namely, the Crash/no Recovery model and the Crash/Recovery model. The assumptions related to the detection of failures that are required to solve Consensus in a given model are particularly emphasized.

Mobile devices offer a valuable resource for distributed learning alongside traditional computers, encouraging energy efficiency and privacy through local computations. However, the hardware limitations of these devices makes it impossible to use classical ...

We introduce quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on “quit” if failures occur, and we relate this problem to the well-known problem of non-blocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.

Nowadays, the integration of home automation systems with smart thermostats is a common trend, designed to enhance resident comfort and conserve energy. The introduction of smart thermostats that can run machine learning algorithms has opened the door for ...

We address the problem of online payments, where users can transfer funds among themselves. We introduce Astro, a system solving this problem efficiently in a decentralized, deterministic, and completely asynchronous manner. Astro builds on the insight tha ...

In the set-agreement problem, n processes seek to agree on at most n−1 different values. This paper determines the weakest failure detector to solve this problem in a message-passing system where processes may fail by crashing. This failure detector, calle ...

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first deterministic specification automata for strict serializability and opacit ...

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. In the ...

Peer-to-peer content dissemination applications suffer immensely from freeriders, i.e., nodes that do not provide their fair share. The Tit-for-Tat (TfT) incentives have received much attention as they help make such systems more robust against freeriding. ...

Exploiting the emerging reality of affordable multi-core architectures goes through providing programmers with simple abstractions that would enable them to easily turn their sequential programs into concurrent ones that expose as much parallelism as possi ...

This article presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple yet important task: Given the performance of an application on a small machine with a handful of cores, ES ...

This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, ...

We prove that transactions cannot be fast in an asynchronous fault-tolerant system. Our result holds in any system where we require transactions to ensure monotonic writes, or any stronger consistency model, such as, causal consistency. Thus, our result unveils an important, and so far unknown, limitation of fast transactions: they are impossible if we want to tolerate the failure of even one server.

This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers in a shared memory system. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are availab ...

Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions ...

Despite the large amount of work on Transactional Memory (TM), little is known about how much liveness it could provide. This paper presents the first formal treatment of the question. We prove that no TM implementation can ensure local progress, the analogous of wait-freedom in the TM context, and we highlight different ways to circumvent the impossibility.

Recent papers [GK03,HT03] define the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing and a majority of processes never crash. In this paper, we generalize the result by presenting the weakest failure detector to solve NBAC in any environment, i.e., without any assumption on the number of processes that can crash. We present the result in a modular manner through determining the weakest failure detector for qu

In [CT96], [FRT99], and [SM95], respectively, it was stated that the weakest failure detector for any of non-blocking atomic commit, terminating reliable broadcast and leader election, is the Perfect failure detector P. This paper presents a counter example of those results.We exhibit a failure detector that is incomparable to P, and yet solves those problems.

Rachid Guerraoui

Chat with Graph Search

The gap in circumventing the impossibility of consensus

Consensus in Asynchronous Distributed Systems: A Concise Guided Tour

ARGO: Overcoming hardware dependence in distributed learning

The weakest failure detectors to solve Quittable Consensus and Non-Blocking Atomic Commit

PePTM: An Efficient and Accurate Personalized P2P Learning Algorithm for Home Thermal Modeling

Online Payments by Merely Broadcasting Messages

The Weakest Failure Detector for Message Passing Set-Agreement

Completeness and Nondeterminism in Model Checking Transactional Memories

On the Complexity of Asynchronous Gossip

On Tracking Freeriders in Gossip Protocols

Leveraging Parallel Nesting in Transactional Memory

ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications

Computing with Reads and Writes in the Absence of Step Contention

The Impossibility of Fast Transactions

The Weakest Failure Detectors to Boost Obstruction-Freedom

Efficient Multi-Word Compare and Swap

On the liveness of transactional memory

On the Liveness of Transactional Memory

Finally the Weakest Failure Detector for Non-Blocking Atomic Commit

On the Hardness of Failure-Sensitive Agreement Problems