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 distributed systems. Specifically, we consider a distributed system that replicates its data at multiple sites, which is prone to partitions, and which is assumed to be available (in the sense that queries are alwa ...

In distributed computing, many papers try to evaluate the message complexity of a distributed system as a function of the number of nodes n. But what about the cost of building the distributed system itself? Assuming that we want to reliably connect n node ...

This paper studies non-cryptographic authenticated broad- cast in radio networks subject to malicious failures. We in- troduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monito ...

Linearizability is a key design methodology for reasoning about implementations of concurrent abstract data types in both shared memory and message passing systems. It provides the illusion that operations execute sequentially and fault-free, despite the a ...

As the classical transactional abstraction is sometimes considered too restrictive in leveraging parallelism, a lot of work has been devoted to devising relaxed transactional models with the goal of improving concurrency. Nevertheless, the quest for improving concurrency has somehow led to neglect one of the most appealing aspects of transactions: software composition, namely, the ability to develop pieces of software independently and compose them into applications that behave correctly in the face of conc

We argue that there is virtually no practical situation in which one should seek a "theoretically wait-free" algorithm at the expense of a state-of-the-art blocking algorithm in the case of search data structures: blocking algorithms are simple, fast, and ...

Causal consistency is an attractive consistency model for geo-replicated data stores. It is provably the strongest model that tolerates network partitions. It avoids the long latencies associated with strong consistency, and, especially when using read-onl ...

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known u ...

We consider the polling problem in a social network where participants care about their reputation: they do not want their vote to be disclosed nor their misbehaving, if any, to be publicly exposed. Assuming this reputation concern, we show that a simple s ...

We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. The algorithmic techniques prop ...

We present AGGREGATHOR, a framework that implements state-of-the-art robust (Byzantine-resilient) distributed stochastic gradient descent. Following the standard parameter server model, we assume that a minority of worker machines can be controlled by an a ...

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write complexity of randomized renaming in an asynchronous environment. At the heart of our new perspective stands an adaptive implementation of a randomized test-and-set object, that has poly-logarithmic step complexity per operation, with high probability. In

A shared memory abstraction can be robustly emulated over an asynchronous message passing system where any process can fail by crashing and possibly recover (crash-recovery model), by having (a) the processes exchange messages to synchronize their read and write operations and (b) log key information on their local stable storage. This paper extends the existing atomicity consistency criterion defined for multi-writer/multi-reader shared memory in a crash-stop model, by providing two new criteria for the cr

The adoption of multi- and many-core architectures for mainstream computing undoubtedly brings profound changes in the way software is developed. In particular, the use of fine grained locking as the multi-core programmer’s coordination methodology is considered by more and more experts as a dead-end. The transactional memory (TM) programming paradigm is a strong contender to become the approach of choice for replacing locks and implementing atomic operations in concurrent programming. Combining sequences o

Many state-machine Byzantine Fault Tolerant (BFT) protocols have been introduced so far. Each protocol addressed a different subset of conditions and use-cases. However, if the underlying conditions of a service span different subsets, choosing a single protocol will likely not be a best fit. This yields robustness and performance issues which may be even worse in services that exhibit fluctuating conditions and workloads. In this paper, we reconcile existing state-machine BFT protocols in a single adaptive

One of the most frequent operations in object-oriented programs is the "instanceof" test, also called the "subtyping" test or the "type inclusion" test. This test determines if a given object is an instance of some type. Surprisingly, despite a lot of research on distributed object-oriented languages and systems, almost no work has been devoted to the implementation of this test in a distributed environment. This paper presents the first algorithm to implement the "subtyping" test on an object received thro

A lot of activity is currently going on to replace the SNMP management architecture with a solution better suited to managing modern IP networks and systems. New candidates include Management by delegation, active networks, and Web-based management. In this exercise, the management community runs the risk of throwing the baby out with the bath water by focusing too much on a few well-known problems exhibited by SNMP (e.g., its poor scalability) and neglecting most of its other characteristics, including tho

What abstractions are useful for expressing distributed interaction? This question has constituted an active area of research in the last decades and several candidates have been proposed, including remote method invocation, tuple spaces and publish/subscribe. How should these abstractions be supported? Through a library or ``directly'' within a language? This important complementary question has sparked less enthousiasm. This paper contributes to addressing this question in the context of Java and the type

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 proce ...

We introduce a new theoretical model of ad hoc mobile computing in which agents have severely restricted memory, highly unpredictable movement and no initial knowledge of the system. Each agent’s memory can store O(1) bits, plus a unique identiﬁer, and O(1 ...

Rachid Guerraoui

Chat with Graph Search

Monotonic Prefix Consistency in Distributed Systems

The Cost of Scaling a Reliable Interconnection Topology

Securing Every Bit: Authenticated Broadcast in Radio Networks

Speculative Linearizability

Composing Relaxed Transactions

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Causal Consistency and Latency Optimality: Friend or Foe? [Extended Version]

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Decentralized Polling with Respectable Participants

Asynchronous Gossip

AGGREGATHOR: Byzantine Machine Learning via Robust Gradient Aggregation

Fast Randomized Test-and-Set and Renaming

Robust Emulations of Shared Memory in a Crash-Recovery Model

The VELOX Transactional Memory Stack

Making BFT Protocols Really Adaptive

Distributed Subtyping

Patterns in SNMP-Based Management

Abstractions for Distributed Programming: Guests or Relatives?

Fast and Robust Memory Reclamation for Concurrent Data Structures

Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures