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 study the issue of data consistency in highly-available distributed systems. Specifically, we consider a distributed system that replicates its data at multiple sites, which is prone to partitions, and which is expected to be highly available. In such a setting, strong consistency, where all replicas of the system apply synchronously every operation, is not possible to implement. However, many weaker consistency criteria that allow a greater number of behaviors than strong consistency, are implementable

We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to pa ...

This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of NBAC, i.e., aborting a transaction as soon as possible if some process votes no,'' and the fast commit property, i.e., committing a transaction as soon as possible when all processes vote yes'' and no process crashes. We also give two algorithms: the fi

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 available, whereas the sufficient ones assume only registers. We show that failure detector P is the weakest to convert any obstruction-free algorithm into a wait-free one, and Omega*, a new failure detector which we introduce in this paper, and which is strict

A contention manager is a shared memory abstraction that boosts progress of obstruction-free algorithms. In this paper, we study the problem of the overhead of non-blocking and wait-free contention managers which use the minimal possible information about failures. More speciﬁcally, we show that ensuring non-blockingness can be achieved with no overhead and that this is not possible when wait-freedom is to be guaranteed. We prove that ensuring wait-freedom has an inherent overhead that, however, can be made

On Transaction Liveness in Replicated Databases F.Pedone and R.Guerraoui This paper makes a first attempt to give a precise characterisation of liveness in replicated database systems. We introduce the notion of liveness degrees, which express the expectation a database user might have about the termination of the transactions, despite concurrency and failures. Our liveness degrees are complementary to the traditional transactional safety degrees (e.g., serializability) and lead to a better characterisation

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key buildi ...

Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, retain the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are more robust in that they only req ...

The propagation of fake news is an increasingly serious concern in social platforms, and designing methods to automatically detect them and limit their spread is an important research challenge. Most existing methods rely on inspecting the content of news ...

Byzantine machine learning (ML) aims to ensure the resilience of distributed learning algorithms to misbehaving (or Byzantine) machines. Although this problem received significant attention, prior works often assume the data held by the machines to be homo ...

Leasing is a very effective way to improve the performance of distributed algorithms without hampering their fault-tolerance. The notion of lease has traditionally been defined using a global notion of time and was hence strongly tied to synchronous system models. This paper introduces a new notion of lease devised for an asynchronous system model. We give the precise properties of our lease abstraction, we show how it can be implemented in an asynchronous system model, and we then illustrate its use by sig

To study the resilience of distributed learning, the “Byzantine" literature considers a strong threat model where workers can report arbitrary gradients to the parameter server. Whereas this model helped obtain several fundamental results, it has sometimes ...

Today, machine learning algorithms are often distributed across multiple machines to leverage more computing power and more data. However, the use of a distributed framework entails a variety of security threats. In particular, some of the machines may mis ...

This paper describes a new consensus algorithm for the asynchronous message passing system model augmented with an unreliable failure detector abstraction: channels are reliable, processes can fail by crashing, and the detection of crashes are not reliable. Our algorithm (a) matches all known consensus lower bounds on (1) failure detection, i.e., \Omega, (2) resilience, i.e., a majority of correct processes, and (3) latency, i.e., two communication steps for a global decision in nice runs (when no process c

Storage is nowadays commonly provided as a service, accessed by clients over a network. A distributed storage service provides clients with the abstraction of a single reliable shared storage device, using a collection of possibly unreliable computing unit ...

We show that, with k-set consensus, any number of processes can emulate k state machines of which at least one progresses. This generalizes the celebrated universality of consensus which enables to build a state machine that always progresses. Besides some interesting extensions and even potential “practical” applications, theoretically, a fundamental ramiﬁcation of our main result, derived by considering the state machines to be interacting read-write threads, is a ﬂagpole to the thesis that distributed co

The success of Bitcoin largely relies on the perception of a fair underlying peer-to-peer protocol: blockchain. Fairness here essentially means that the reward (in bitcoins) given to any participant that helps maintain the consistency of the protocol by mi ...

GARF est un environnement à objets permettant la programmation modulaire d'applications distribuées résistantes aux pannes. Cet article présente la bibliothèque de classes offertes au programmeur par GARF, pour gérer l'expression de la concurrence et de son contrôle. La mise en oeuvre des mécanismes introduisant la concurrence, ainsi que plusieurs classes proposant divers types de contrôle de concurrence intra-objet, sont présentées. L'extension de certaines de ces classes au contrôle de concurrence inter-o

Obstruction-free implementations of concurrent ob jects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this paper, we study this ...

We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as failure prone server processes implementing the data structure. We determine the exact conditions under which every read operation involves one-round of communication with the servers. These conditions relate the number of readers to the tolerated number of faulty servers, in a general model with crash and arbitrary failu

Rachid Guerraoui

Chat with Graph Search

Why You Can't Beat Blockchains: Consistency and High Availability in Distributed Systems

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

The Weakest Failure Detectors to Boost Obstruction-Freedom

Boosting Obstruction-Freedom with Low Overhead

On Transaction Liveness in Replicated Databases

How to Allocate Tasks Asynchronously

Leaderless Consensus

G-Fake: Tell Me How It is Shared and I Shall Tell You If It is Fake

Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity

Asynchronous Leasing

An Equivalence Between Data Poisoning and Byzantine Gradient Attacks

Robust Machine Learning - Distributed Methods for Safe AI

Fast Indulgent Consensus with Zero Degradation

Reliable Distributed Storage

Generalizing State Machine Replication

On the Unfairness of Blockchain

Abstractions pour la Programmation Concurrente dans GARF

The Complexity of Obstruction-Free Implementations

How Fast can a Distributed Atomic Read be?