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.

Byzantine resilience emerged as a prominent topic within the distributed machine learning community. Essentially, the goal is to enhance distributed optimization algorithms, such as distributed SGD, in a way that guarantees convergence despite the presence ...

State machine replication reduces distributed to centralized computing. Any sequential service, modeled by a state machine, can be replicated over any number of processes and made highly available to all of them. At the heart of this fundamental reduction ...

Transactions are commonly described as being ACID: All-or-nothing, Consistent, Isolated and Durable. However, although these words convey a powerful intuition, the ACID properties have never been given a precise semantics in a way that disentangles each property from the others. Among the benefits of such a semantics would be the ability to trade-off the value of a property against the cost of its implementation. This paper gives a sound equational semantics for the transaction properties. We define three c

Cloud computing offers an appealing business model and it is tempting for companies to delegate their IT services to the cloud. Yet, a company might ﬁnd it risky to do so for sensible services and to depend entirely on a single provider, which can be vulnerable and constitute a clearly identiﬁed target for attackers. We explore in this paper a replication approach where copies of the same IT service are placed on several (cumulus) clouds that are not only independent but actually unaware of each other. Repl

A plethora of optimized mutex lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and locks. Unfortunately, there is currently no broad study of the behavior of these optimized lock alg ...

Aggregation of streamed data is key to the expansion of the Internet of Things. This paper addresses the problem of designing a topology for reliably aggregating data flows from many devices arriving at a datacenter. Reliability here means ensuring operati ...

Erasure coded storage provides a cheap and space efficient way to tolerate failures through the use of networked commodity servers. Erasure coded data is kept on n different servers out of which f can fail. By combining encoded blocks from n-f servers, the data can be read back. This paper presents ORCAS, an Optimistic eRasure Coded Atomic Storage algorithm. ORCAS is the first wait-free, optimally resilient (n > 2f) erasure coded storage for systems with asynchronous processes that can crash and recover. OR

This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t < S/2) and req

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 blocks. The minimal synchrony assumptions on communication, which enable to implement the failure detection mechanism, are studied separately. Such synchrony assumptions are typically expressed as eventual guarantees that need to hold, after some point in t

Self-stabilization ensures that, after any transient fault, the system recovers in a finite time and eventually exhibits correct behavior. Speculation consists in guaranteeing that the system satisfies its requirements for any execution but exhibits significantly better performances for a subset of executions that are more probable. A speculative protocol is in this sense supposed to be both robust and efficient in practice. We introduce the notion of speculative stabilization which we illustrate through th

Non-volatile memory (NVM) promises fast, byte-addressable and durable storage, with raw access latencies in the same order of magnitude as DRAM. But in order to take advantage of the durability of NVM, programmers need to design persistent objects which ma ...

This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault d ...

Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the Database State Machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and alleviates the need for atomic commitment. Transaction

Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the database state machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and no atomic commitment is necessary. Transaction commit

The perfectly synchronized round model provides the powerful abstraction of crash-stop failures with atomic message delivery. This abstraction makes distributed programming very easy. We present an implementation of this abstraction in a distributed system with general message omissions. Protocols devised using our abstraction (i.e., in the perfectly synchronized round model) are automatically transformed into protocols for the omission model. The transformation is achieved using a round shifting technique

This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods of asynchrony as in the Internet. The measure expresses the ability of processes to reach a consensus decision in a minimal number of rounds of information exchange, as a function of (a) the ability to use authentication and (b) the number of actual proces

This paper asks how much liveness a transactional memory (TM) implementation can guarantee. We first devise a formal framework for reasoning about liveness properties of TMs. Then, we prove that the strongest liveness property that a TM can ensure in an asynchronous system with transaction crashes is a property that we call "global progress". This property is analogous to lock-freedom for shared-memory objects and is indeed guaranteed by certain TM implementations, e.g., OSTM. We also prove that the presenc

Achieving submillisecond response times in a managed language environment such as Java or C# requires overcoming signiﬁcant challenges. In this article, we propose Reﬂexes, a programming model and runtime system infrastructure that lets developers seamless ...

This paper presents an algorithm to ensure the atomicity of a distributed storage that can be read and written by any number of clients. In failure-free and synchronous situations, and even if there is contention, our algorithm has a high write throughput ...

Byzantine Agreement (BA) enables n processes to reach consensus on a common valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from their prescribed protocol. Despite its significance, the optimal communic ...

Rachid Guerraoui

Chat with Graph Search

Byzantine Machine Learning Made Easy By Resilient Averaging of Momentums

Generalized Universality

An Equational Theory for Transactions

Trustful Cumulus Clouds

Lock-Unlock: Is That All? A Pragmatic Analysis of Locking in Software Systems

Frugal Topology Construction for Stream Aggregation in the Cloud

Optimistic Erasure Coded Distributed Storage

How fast can a distributed atomic read be?

Never Say Never Probabilistic & Temporal Failure Detectors (Extended)

Introducing Speculation in Self-Stabilization: An Application to Mutual Exclusion

The Inherent Cost of Remembering Consistently

The Inherent Price of Indulgence

The Database State Machine Approach

The Database State Machine Approach

Distributed Programming for Dummies: A Shifting Transformation Technique

The Complexity of Asynchronous Byzantine Consensus

How Live Can a Transactional Memory Be?

Reﬂexes: Abstractions for Integrating Highly Responsive Tasks into Java Applications

A High Throughput Atomic Storage Algorithm

DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication