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 its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. If we consider an asynchronous messagepassing environment in which processes might fail by crashing, and assume that a majority ...

This paper presents a computing model for resource-limited mobile devices. The originality of the model lies in the integration of a strongly-typed 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 log

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

Software Transactional Memory (STM) promises to simplify concurrent programming without requiring specific hardware support. Yet, STM’s credibility lies on the extent to which it enables to leverage multicores and outperform sequential code. A recent CACM ...

As the classic transactional abstraction is sometimes considered too restrictive in leveraging parallelism, a lot of work has been devoted to devising relaxed transactional models with the goal of improving concurrency. Nevertheless, the quest for improvin ...

This paper presents Atum, a group communication middleware for a large, dynamic, and hostile environment. At the heart of Atum lies the novel concept of volatile groups: small, dynamic groups of nodes, each executing a state machine replication protocol, organized in a flexible overlay. Using volatile groups, Atum scatters faulty nodes evenly among groups, and then masks each individual fault inside its group. To broadcast messages among volatile groups, Atum runs a gossip protocol across the overlay. We re

Problems of pattern formation have been extensively studied in distributed computing. One of this problems is the gathering problem: agents must gather at a same position in a distributed manner. When gathering is not possible, a close problem is the conve ...

The possibility of adversarial (a.k.a., Byzantine) clients makes federated learning (FL) prone to arbitrary manipulation. The natural approach to robustify FL against adversarial clients is to replace the simple averaging operation at the server in the standard FedAvg algorithm by a robust averaging rule. While a significant amount of work has been devoted to studying the convergence of federated robust averaging (which we denote by FedRo), prior work has largely ignored the impact of client subsampling and

Software transactional memory (STM) is a promising technique for controlling concurrency in modern multi-processor architectures. STM aims to be more scalable than coarse-grained locking and easier to use than fine-grained locks. However, STM implementations have yet to demonstrate that their runtime overheads are acceptable. To date, empiric evaluations of these implementations have suffered from the lack of realistic benchmarks. Measuring performance of an STM in an overly simplified setting can be at bes

Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some specific impossibility, e. g., consen ...

Although much research has been devoted to designing and experimenting on ad hoc networks of tiny devices, very little has focussed on devising theoretical models to capture the inherent power and limitations of such networks. A notable exception is the population protocol model of Angluin et al. [2]. This model is simple and elegant but is sometimes considered too restrictive because of its anonymity: mobile agents have no identities and all look the same. We investigate in this paper the inherent power of

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This paper is the first to formally define the progress semantics of lock-based TMs, which are considered the most effective in practice. We use our semantics to reduce the problems of reasoning about the correctness and computability power of lock-based TMs to tho

Establishing the scalability of a concurrent algorithm a priori, before implementing and evaluating it on a concrete multi-core platform, seems difficult, if not impossible. In the context of search data structures however, according to all practical work ...

It is appealing to implement publish/subscribe systems in a peer to peer (P2P) manner to circumvent the scalability issues of broker-based (semi-decentralized) systems and simplify the deployment. While existing P2P generic infrastructures provide a scalable support for topic-based publish-subscribe systems, they are not well adapted to content-based ones. In this paper, we advocate the need for dedicated overlay networks -where the overlay structure reflects the actual structure of the underlying applicati

In this paper, we present PDP, a distributed polling protocol that enables a set of participants to gather their opinion on a common interest without revealing their point of view. PDP does not rely on any centralized authority or on heavyweight cryptograp ...

Many distributed storage systems are transactional and a lot of work has been devoted to optimizing their performance, especially the performance of read-only transactions that are considered the most frequent in practice. Yet, the results obtained so far ...

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 approaches are typically transa ...

Conducting a thorough performance evaluation of an STM is very time consuming. Depressingly, even with all this effort, and even with the same application, it can still be hard to predict the performance if the number of underlying threads on which the application needs to be deployed is different than those of the experiment. Basically, one might have to conduct an entire set of new experiments to get some understanding of the performance of the STM with the new number of threads. We propose a pragmatic ap

In a non-uniform memory access machine, the placement of software threads to hardware cores can have a significant effect on the performance of concurrent applications. Detecting the best possible placement for each application is a necessity for thread sc ...

Software transactional memory (STM) is a promising technique for controlling concurrency in modern multi-processor architectures. STM aims to be more scalable than explicit coarse-grained locking and easier to use than fine-grained locking. However, STM im ...

Rachid Guerraoui

Chat with Graph Search

The weakest failure detector for eventual consistency

Frugal Mobile Objects

Refined quorum systems

Why STM can be more than a Research Toy

Composing Relaxed Transactions

Atum: Scalable Group Communication Using Volatile Groups

Exploring The Borderlands Of The Gathering Problem

Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates

STMBench7: A Benchmark for Software Transactional Memory

On the weakest failure detector ever

Even Small Birds are Unique: Population Protocols with Identifiers

The Semantics of Progress in Lock-Based Transactional Memory

Sequential Proximity: Towards Provably Scalable Concurrent Search Algorithms

GosSkip: a Gossip-based Structured Overlay Network for Efficient Content-based Filtering

A Distributed Polling with Probabilistic Privacy

Distributed Transactions: Dissecting the Nightmare

Log-Free Concurrent Data Structures

Predicting the Scalability of an STM: A Pragmatic Approach

Thread-Placement Learning

STMBench7: A Benchmark for Software Transactional Memory