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.

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal ...

This paper presents a new, non-binary measure of the reliability of broadcast algorithms, called Delta-Reliability. This measure quantifies the reliability of practical broadcast algorithms that, on the one hand, were devised with some form of reliability in mind, but, on the other hand, are not considered reliable according to the ``traditional'' notion of broadcast reliability [HT94]. Our specification of Delta-Reliability suggests a further step towards bridging the gap between theory and practice in the

The history of distributed computing is full of trade-offs between safety and liveness. For instance, one of the most celebrated results in the field, namely the impossibility of consensus in an asynchronous system basically says that we cannot devise an a ...

This paper presents a pragmatic way to build a Reliable CORBA Event Service. Our approach is pragmatic in the sense that, rather than building the service from scratch, we show how to obtain it, through a simple transformation, from any standard (unreliable) CORBA 2.0 Event Service. Our extension does not introduce any modification to the CORBA specification, nor any communication overhead. The Reliable CORBA Event Service provides the adequate semantics for building reliable notification-based applications

This paper presents the most exhaustive study of synchronization to date. We span multiple layers, from hardware cache-coherence protocols up to high-level concurrent software. We do so on different types of architectures, from single-socket - uniform and non-uniform - to multi-socket - directory and broadcast-based - many-cores. We draw a set of observations that, roughly speaking, imply that scalability of synchronization is mainly a property of the hardware. © 2013 ACM.

This paper presents a computing model for resource-limited mobile devices. The originality of the model lies in the integration of a stronglytyped event-based communication paradigm with abstractions for frugal control, assuming a small footprint runtime. With our model, an application consists of a set of distributed reactive objects, called FROBs, that communicate through typed events and dynamically adapt their behavior reacting to notifications typically based on resource availability. FROBs have a logi

We establish a theorem called the PCL theorem, which states that it is impossible to design a transactional memory algorithm that ensures (1) parallelism, i.e., transactions do not need to synchronize unless they access the same application objects, (2) ve ...

Programming with replicated objects is difficult. Developers must face the fundamental trade-off between consistency and performance head on, while struggling with the complexity of distributed storage stacks. We introduce Correctables, a novel abstraction ...

Keywords: distributed systems, fault-tolerance, consensus, efficiency, synchronous system, asynchronous system, failure detector. We compare, in terms of solvability and efficiency, the synchronous model, noted S_S, with the asynchronous model augmented with a perfect failure detector, noted S_P. We first exhibit a problem that, although time-free, is solvable in S_S but not in S_P. We then examine whether one of these two models allows more efficient solutions for designing fault-tolerant applications. In

Scaling to a large number of cores with non-uniform communication latency and unpredictable response time may call for viewing a modern many-core architecture as a distributed system. In this view, the cores replicate shared data and ensure consistency among replicas through a message-passing based agreement protocol. In this paper, we present the first in-depth study of message-passing agreement on many-cores. In particular, we focus on the possibility of such a protocol being non-blocking. We highlight a

A computation scheme among n parties is fair if no party obtains the computation result unless all other n-1 parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower bound on the message complexity of optimistic fair computation for n parties among which n-1 can be malicious in an asynchronous network. We do so by relating the optimal message complexity

We consider the problem of making a multi-agent system (MAS) resilient to Byzantine failures through replication. We consider a very general model of MAS, where randomness can be involved in the behavior of each agent. We propose the first universal scheme ...

The vast majority of papers on distributed computing assume that processes are assigned unique identifiers before computation begins. But is this assumption necessary? What if processes do not have unique identifiers or do not wish to divulge them for reas ...

We study eﬃcient 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 a number of servers implementing the data structure. We determine the exact conditions under which every read and write involves one round of communication with the servers. These conditions relate the number of readers to the tolerated number of faulty servers and the nature of these failures.

This paper presents the Weight-Watcher service. This service aims at providing resource consumption measurements and estimations for software executing on resource constrained devices. By using the Weight-Watcher, software components can continuously adapt ...

Data centers increasingly host mutually distrustful users on shared infrastructure. A powerful tool to safeguard such users are digital signatures. Digital signatures have revolutionized Internet-scale applications, but current signatures are too slow for ...

In a transactional system, an atomic commitment protocol ensures that for any transaction, all data managers agree on the same outcome: commit or abort. A non-blocking atomic commitment protocol enables an outcome to be decided at every correct data manager despite the failure of others. It is well known that the famous Two Phase Commit protocol (2PC) is a blocking protocol, whereas the Three Phase Commit protocol (3PC) is a non-blocking protocol. Both protocols are centralized. In this paper, we discuss a

Locks are a natural place for improving the energy efficiency of software systems. First, concurrent systems are mainstream and when their threads synchronize, they typically do it with locks. Second, locks are well-defined abstractions, hence changing the ...

Building correct and efﬁcient concurrent algorithms is known to be a difﬁcult problem of fundamental importance. To achieve ef- ﬁciency, designers try to remove unnecessary and costly synchro- nization. However, not only is this manual trial-and-error process ad-hoc, time consuming and error-prone, but it often leaves design- ers pondering the question of: is it inherently impossible to elimi- nate certain synchronization, or is it that I was unable to eliminate it on this attempt and I should keep trying?

Transactional memory is perceived as an appealing alternative to critical sections for general purpose concurrent programming. Despite the large amount of recent work on transactional memory implementations, however, its actual specification has never been precisely defined. This paper presents \emph{opacity}, a new correctness criterion for transactional memory systems. Opacity extends the notion of strict serializability, itself a strong form of the classical serializability property, with the requirement

Rachid Guerraoui

Chat with Graph Search

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Delta-Reliability

Safety-Liveness Exclusion in Distributed Computing

Reliable CORBA Event Channels

Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask

Frugal Mobile Objects

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

Incremental Consistency Guarantees for Replicated Objects

Synchronous System and Perfect Failure Detector: solvability and efficiency issues

Consensus Inside

Optimal Fair Computation

Byzantine-Resilient Multi-Agent System

Anonymous and fault-tolerant shared-memory computing

Fast Access to Distributed Atomic Memory

The Weight-Watcher Service and its Lightweight Implementation

DSig: Breaking the Barrier of Signatures in Data Centers

The Decentralized Non-Blocking Atomic Commitment Protocol

Unlocking Energy

Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated

Opacity: A Correctness Condition for Transactional Memory