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.

The Byzantine agreement problem requires a set of

n

processes to agree on a value sent by a transmitter, despite a subset of

b

processes behaving in an arbitrary, i.e. Byzantine, manner and sending corrupted messages to all processes in the system. It is well known that the problem has a solution in a (an eventually) synchronous message passing distributed system iff the number of processes in the Byzantine subset is less than one third of the total number of processes, i.e. iff

n > 3b+1

. The rest of

This paper presents a distributed algorithm to disseminate events in a publish/subscribe system, where processes publish events of certain topics, organized in a hierarchy, and expect events of topics they subscribed to. Every topic defines a dynamic notion of ``community'', gathering the processes which publish on that topic or subscribe to it. Our algorithm is completely decentralized (no brokers), yet does not require from any process to ever receive, store or forward, events from a community it is not p

Current approaches to model checking distributed systems reduce the problem to that of model checking centralized systems: global states involving all nodes and communication links are systematically explored. The frequent changes in the network element of the global states lead however to a rapid state explosion and make it impossible to model check any non-trivial distributed system. We explore in this paper an alternative: a local approach where the network is ignored, a priori: only the local nodes’ sta

Shared objects are the means by which processes gather and exchange information about the state of a distributed system. Objects that disclose more information about the system are therefore more desirable. In this paper, we propose the schedule reconstruc ...

A universal construction is an algorithm that transforms any object with a sequential specification into a wait-free and linearizable implementation of that object. This paper presents a novel universal construction algorithm for a message-passing system with process crash failures. Our algorithm relies on two fine-grained underlying abstractions: a weak form of leader election, and a one-shot form of register. Our algorithm is \emp{indulgent}, \emp{efficient} and \emp{generic}. Being indulgent intuitively

In reinforcement learning, agents learn by performing actions and observing their outcomes. Sometimes, it is desirable for a human operator to \textit{interrupt} an agent in order to prevent dangerous situations from happening. Yet, as part of their learni ...

We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard's index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and s ...

We introduce a generalization of the atomic snapshot object, which we call the partial snapshot object. This object stores a vector of values. Processes may write components of the vector individually or atomically scan any subset of the components. We inv ...

This paper presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple, yet important task: given the performance of an application on a small machine with a handful of cores, EST ...

Many reliable distributed systems are consensus-based and typically operate under two modes: a fast normal mode in failure-free periods, and a slower recovery mode following failures. A lot of work has been devoted to optimizing the normal mode, but little has been devoted to optimizing the recovery mode. This work seeks to understand whether the recovery mode is inherently slower than the normal mode. We focus on consensus algorithms that tolerate arbitrary periods of asynchrony as well as the crash of a m

This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C ava ...

This paper presents a simple framework unifying a family of consensus algorithms that can tolerate process crash failures and asynchronous periods of the network, also called indulgent consensus algorithms. Key to the framework is a new abstraction we intr ...

No t-resilient Byzantine Agreement (or Reliable Broadcast) protocol can guarantee agreement among n correct processes in a non-synchronous network if the actual number of faulty processes f is ≥n−2t. This limitation highlights the need to augment such fragile protocols with mechanisms that detect safety violations, such as forensic support and accountability. This paper introduces simple and efficient techniques to address this challenge by proposing a new generic transformation, ABC++. The transformation l

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

Non-volatile RAM (NVRAM) makes it possible for data structures to tolerate transient failures, assuming however that programmers have designed these structures such that their consistency is preserved upon recovery. Previous ap- proaches are typically tran ...

Large language models (LLMs) achieve remarkable performance across domains but remain prone to hallucinations and inconsistencies. Retrieval-augmented generation (RAG) mitigates these issues by augmenting model inputs with relevant documents retrieved from external sources. In many real-world scenarios, relevant knowledge is fragmented across organizations or institutions, motivating the need for federated search mechanisms that can aggregate results from heterogeneous data sources without centralizing the

Gossip-based protocols are now acknowledged as a sound basis to implement collaborative high-bandwidth content dissemination: content location is disseminated through gossip, the actual contents being subsequently pulled. In this paper, we present HEAP, HEterogeneity-Aware Gossip Protocol, where nodes dynamically adjust their contribution to gossip dissemination according to their capabilities. Using a continuous, itself gossip-based, approximation of relative capabilities, HEAP dynamically leverages the mo

A concurrent object is an object that can be concurrently accessed by several processes. It has been shown by Maurice Herlihy that any concurrent object O defined by a sequential specification can be wait-free implemented from reliable atomic registers (shared variables) and consensus objects. Wait-free means that any invocation of an operation of the object O issued by a non-faulty process does terminate, whatever the behavior of the other processes (e.g., despite the fact they are very slow or even have c

We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard’s index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and s ...

Rachid Guerraoui

Chat with Graph Search

Beyond One Third Byzantine Failures

Community-Aware Event Dissemination

Local Model Checking

The Disclosure Power of Shared Objects

An Efficient Universal Construction for Message-Passing Systems

Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning

Model Checking a Networked System Without the Network

GoldFinger: Fast & Approximate Jaccard for Efficient KNN Graph Constructions

Partial Snapshot Objects

ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications

The Overhead of Consensus Failure Recovery

Interference-Resilient Information Exchange

The Alpha of Indulgent Consensus

Scalable Accountable Byzantine Agreement and Beyond

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

Log-Free Concurrent Data Structures

Efficient Federated Search for Retrieval-Augmented Generation Using Lightweight Routing

Gossiping Capabilities

From unreliable objects to reliable objects: The case of atomic registers and consensus

Smaller, Faster & Lighter KNN Graph Constructions