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.

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t + 1. In other words, an adversary that can crash any subset of size at most t can prevent the processes from agreeing on t values. But what about all the other 22n−1−(n+1) adversaries that are not uniform in this sense and might crash certain combination of processes and not others? This paper presents a precise way

This paper presents a computing model for resource-limited mobile devices that might be ubiquitously deployed in private and business environments. The model integrates a strongly-typed event-based communication paradigm with abstractions for frugal contro ...

The celebrated Paxos protocol implements a reliable service as a state machine replicated over several machines. Replication provides reliability against permanent failures and availability against temporary crash failures. Whereas, in theory, Paxos can tolerate any number f of crash failures using 2f + 1 replicas, in practice, it is often appealing to use it in order to tolerate a single failure using three replicas for the probability of two simultaneous failures is sometimes considered low enough. We sho

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement ...

This paper addresses the fundamental tradeoffs in event systems between scalability (of event filtering, routing, and delivery mechanisms), expressiveness (when describing interests in events), and event safety (ensuring encapsulation and type-safe interaction with polymorphic events). We point out some ramifications underlying these tradeoffs and we propose a pragmatic approach to handle them. We achieve scalability using a multi-stage filtering strategy that combines approximate and perfect matching techn

Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post-deployment. Despite this importance, existing approaches are often heuristic and lack formal g ...

We define the Abortable Linearizable Module automaton (ALM for short) and prove its key composition property using the IOA theory of HOLCF. The ALM is at the heart of the Speculative Linearizability framework. This framework simplifies devising correct speculative algorithms by enabling their decomposition into independent modules that can be analyzed and proved correct in isolation. It is particularly useful when working in a distributed environment, where the need to tolerate faults and asynchrony has mad

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 algorithm that deterministically ensures consensus agreement and validity (i.e., safety) on the one hand, and consensus wait-freedom (i.e., liveness) on the other hand. The motivation of this work is to study the extent to which safety and liveness properti

We study private computations in a system of tiny mobile agents. We consider the mobile population protocol model of Angluin et al. [2] and ask what can be computed without ever revealing any input to a curious adversary. We show that any computable predic ...

The geometric median, an instrumental component of the secure machine learning toolbox, is known to be effective when robustly aggregating models (or gradients), gathered from potentially malicious (or strategic) users. What is less known is the extent to ...

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale distribut ...

We introduce the notion of permissiveness in transactional memories (TM). Intuitively, a TM is permissive if it never aborts a transaction when it need not. More specifically, a TM is permissive with respect to a safety property

p

if the TM accepts every ...

This paper presents a replication algorithm that implements a highly-available, non deterministic state machine.

This paper addresses the problem of broadcasting messages in a reliable and totally ordered manner when processes and channels may crash and recover, or crash and never recover. We present a suite of specifications of reliable and total order broadcast primitives and we describe algorithms that implement those specifications. Our approach is modular and incremental. It is modular in the sense that the properties of broadcast primitives are first given separately and then composed: this provides a comprehens

Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spen ...

Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring specific software solutions (STM). So far, however, STMs have been mainly evaluated and optimized for smaller scale benchmarks. We revisit the main STM design choices from the perspective of complex workloads and propose a new STM, which we call SwissTM. In sho

This paper extends the failure detector approach from crash-stop failures to muteness failures. Muteness failures are malicious failures in which a process stops sending algorithm messages, but might continue to send other messages, e.g., ``I am alive'' messages. The paper presents both the specification of a muteness failure detector, denoted ny M and an implementation of M in a partial synchrony model. We show that, modulo a simple modification, a consensus algorithm that has been designed in a crash-

This paper extends the failures detector approach from crash-stop failures to muteness failures. Muteness failures are malicious failures in which a process stops sending algorithm messages, but might continue to send other messages, e.g. 'I-am-alive' messages. The paper presents both the specification of a muteness failure detector, denoted by MA, and an implementation of MA in a partial synchrony model (there are bounds on message latency and clock skew, but these bounds are unknown and hold only after so

Byzantine-resilient Stochastic Gradient Descent (SGD) aims at shielding model training from Byzantine faults, be they ill-labeled training datapoints, exploited software/hardware vulnerabilities, or malicious worker nodes in a distributed setting. Two rece ...

Rachid Guerraoui

Chat with Graph Search

The disagreement power of an adversary

Pervasive Computing with Frugal Objects

One Acceptor is Enough

On the Validity of Consensus

Event Systems : How to Have Your Cake and Eat It Too

The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning

Abortable Linearizable Modules

Stretching Transactional Memory

Safety-Liveness Exclusion in Distributed Computing

Secretive Birds: Privacy in Population Protocols

On the Strategyproofness of the Geometric Median

Heterogeneous Gossip

Permissiveness in Transactional Memories

Democratizing the Parliament

Reliable and Total Order Broadcast in the Crash-Recovery Model

The Consensus Number of a Cryptocurrency

Stretching Transactional Memory

Muteness Failure Detectors: Specification and Implementation

Muteness Failure Detectors, Specification and Implementation

Distributed Momentum for Byzantine-resilient Stochastic Gradient Descent