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.

In a non-synchronous system with n processes, no t(0)-resilient (deterministic or probabilistic) Byzantine consensus protocol can prevent a disagreement among correct processes if the number of faulty processes is > n - 2t(0). Therefore, the community defi ...

In this paper we present a technique for automatically assessing the amount of damage a small number of participant nodes can inﬂict on the overall performance of a large distributed system. We propose a feedback-driven tool that synthesizes malicious node ...

We study the problem of secure communication in a multi-channel, single-hop radio network with a malicious adversary that can cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution ...

The rapidly increasing amount of user-generated content in social tagging systems provides a huge source of information. Yet, performing effective search in these systems is very challenging, especially when we seek the most appropriate items that match a ...

We present WhatsUp, a collaborative filtering system for disseminating news items in a large-scale dynamic setting with no central authority. WhatsUp constructs an implicit social network based on user profiles that express the opinions of users about the ...

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first \emph{deterministic} specification automata for strict serializability and ...

Existing approaches to distribute Generative Adversarial Networks (GANs) either (i) fail to scale for they typically put the two components of a GAN (the generator and the discriminator) on different machines, inducing significant communication overhead, o ...

Total order broadcast is a fundamental communication primitive that plays a central role in bringing cheap software-based high availability to a wide array of services. This paper studies the practical performance of such a primitive on a cluster of homoge ...

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

This paper addresses the question of the weakest failure detector to solve the Non-Blocking Atomic Commit (NBAC) problem in an asynchronous system. We define the set A of timeless failure detectors which excludes detectors that provide information about global time but includes all known meaningful failure detectors such as P and P [CT96]. We show that, within A, the weakest failure detector for NBAC is ?P+S.

While Machine Learning (ML) applications have shown impressive achievements in tasks such as computer vision, NLP, and control problems, such achievements were possible, first and foremost, in the best-case-scenario setting. Unfortunately, settings where M ...

This paper addresses the question of the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing. We define a failure detector, denoted by X, which we show to be sufficient to solve NBAC with a majority of correct processes. Then we give an algorithm which, no matter how many processes may crash, uses any failure detector that solves NBAC to emulate X, i.e., we prove that \X~is also necessary for solving NBAC. The re

We present multiversion timestamp locking (MVTL), a new genre of multiversion concurrency control algorithms for serializable transactions. The key idea behind MVTL is simple: lock individual timestamps instead of locking objects. After presenting a generi ...

We present Epidemic Learning ( EL ), a simple yet powerful decentralized learning (DL) algorithm that leverages changing communication topologies to achieve faster model convergence compared to conventional DL approaches. At each round of EL, each node sen ...

We propose a new mechanism to preserve privacy while leveraging user profiles in distributed recommender systems. Our mechanism relies on (i) an original obfuscation scheme to hide the exact profiles of users without significantly decreasing their utility, ...

Federated learning (FL) is very appealing for its privacy benefits: essentially, a global model is trained with updates computed on mobile devices while keeping the data of users local. Standard FL infrastructures are however designed to have no energy or ...

We consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of O(n^2) in an n nodes system, we present SPP (Secure an ...

This paper discusses the relationship between the {\em Non-\Blocking Atomic Commitment problem (NB-AC)} and the Consensus problem in asynchronous systems with unreliable failure detectors. We first confirm that NB-AC is harder than Consensus. In contrast to Consensus, NB-AC is impossible to solve with unreliable failure detectors even with a single crash failure. We define a weaker problem than NB-AC, called Non-Blocking Weak Atomic Commitment (NB-WAC), which is sufficient to solve for most practical situa

Modern Byzantine fault-tolerant state machine replication (BFT) protocols involve about 20.000 lines of challenging C++ code encompassing synchronization, networking and cryptography. They are notoriously difficult to develop, test and prove. We present a new abstraction to simplify these tasks. We treat a BFT protocol as a composition of instances of our abstraction. Each instance is developed and analyzed independently. To illustrate our approach, we first show how, with our abstraction, the benefits of a

We introduce "asynchronized concurrency (ASCY),'' a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures (CSDSs) to resemble that of their sequential counterparts. We argue that ASCY ...

Rachid Guerraoui

Chat with Graph Search

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Automated Vulnerability Discovery in Distributed Systems

Secure Communication Over Radio Channels

Personalizing Top-k Processing Online in a Peer-to-Peer Social Tagging Network

WHATSUP: A Decentralized Instant News Recommender

Completeness and Nondeterminism in Model Checking Transactional Memories

FeGAN: Scaling Distributed GANs

High Throughput Total Order Broadcast for Cluster Environments

The consensus number of a cryptocurrency (extended version)

On the Weakest Failure Detector for Non-Blocking Atomic Commit.

Adversarial Evasion on LLMs

The Weakest Failure Detector for Non-Blocking Atomic Commit

Locking Timestamps versus Locking Objects

Epidemic Learning: Boosting Decentralized Learning with Randomized Communication

Privacy-Preserving Distributed Collaborative Filtering

FLEET: Online Federated Learning via Staleness Awareness and Performance Prediction

Scalable and Secure Polling in Dynamic Distributed Networks

Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus

The Next 700 BFT Protocols

Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures