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.

This paper defines the problem of Scalable Secure computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a symmetric function f : V-n -> U of their inputs in a set of constant si ...

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been ...

This paper presents GosSkip, a self organizing and fully distributed overlay that provides a scalable support to data storage and retrieval in dynamic environments. The structure of GosSkip, while initially possibly chaotic, eventually matches a perfect se ...

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component ...

With the development of neural networks based machine learning and their usage in mission critical applications, voices are rising against the \textit{black box} aspect of neural networks as it becomes crucial to understand their limits and capabilities. W ...

Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as ...

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automatically whether the executions of an implementation of a data structure are causally consistent. We consider two problems: (1) checking whether one single execution is causally consistent, which is relevant for developing testing and bug finding algorithms, and

This paper introduces Carbon, a high-throughput system enabling asynchronous (safe) and consensus-free (efficient) payments and votes within a dynamic set of clients. Carbon is operated by a dynamic set of validators that may be reconfigured asynchronously ...

Could a gradient aggregation rule (GAR) for distributed machine learning be both robust and fast? This paper answers by the affirmative through Multi-Bulyan. Given n workers, f of which are arbitrary malicious (Byzantine) and m = n − f are not, we prove th ...

This paper defines the problem of Scalable Secure Computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a function f : V -> U of their inputs in a set of constant size, in a scalable and secure way. Scalability means that the message and computational complexity of the distributed computation is at most O(root n . polylog n). Security encompasses (1) accuracy and (2) privacy: accuracy holds when the distance from the output to th

Linearizability is a key design methodology for reasoning about implementations of concurrent abstract data types in both shared memory and message passing systems. It provides the illusion that operations execute sequentially and fault-free, despite the asynchrony and faults inherent to a concurrent system, especially a distributed one. A key property of linearizability is inter-object composability: implementations of linearizable objects can be composed into more complex linearizable objects. However, de

We introduce a new distributed computing model called m&m that allows processes to both pass messages and share memory. Motivated by recent hardware trends, we find that this model improves the power of the pure message-passing and shared-memory models. As ...

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the n ...

Transactional memory (TM) is perceived as an appealing alternative to critical sections for general purpose concurrent programming. Despite the large amount of recent work on TM implementations, however, very little effort has been devoted to precisely def ...

Set agreement, where processors decisions constitute a set of outputs, is notoriously harder to analyze than consensus where the decisions are restricted to a single output. This is because the topological questions that underly set agreement are not about simple connectivity as in consensus. Analyzing set agreement inspired the discovery of the relation between topology and distributed algorithms, and consequently the impossibility of set agreement. Yet, the application of topological reasoning has been to

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

Subtyping tests are essential in typed publish/subscribe infrastructures, especially when the underlying programming language supports subtype conformance, as in Java or C#. These tests are particularly challenging when the publish/subscribe infrastructure ...

Distributed computing is one of the major trends in the computer industry. As systems become more distributed, they also become more complex and have to deal with new kinds of problems, such as partial crashes and link failures. While many middleware architectures have emerged to answer the growing demand in distributed technologies, most of them do not provide any kind of fault tolerance mechanisms. In this paper, we discuss the addition of object group support to CORBA. We describe three approaches: integ

Rachid Guerraoui

Chat with Graph Search

Computing in social networks

Robust Collaborative Learning with Linear Gradient Overhead

GosSkip, an Efficient, Fault-Tolerant and Self Organizing Overlay Using Gossip-based Construction and Skip-Lists principles

Tight Bounds for Asynchronous Renaming

Genuinely Distributed Byzantine Machine Learning

On The Robustness of a Neural Network

Scalable Byzantine Reliable Broadcast

On Verifying Causal Consistency

Carbon: Scaling Trusted Payments with Untrusted Machines

Fast and Robust Distributed Learning in High Dimension

Computing in Social Networks

Speculative Linearizability

On verifying causal consistency

Passing Messages while Sharing Memory

The Time-Complexity of Local Decision in Distributed Agreement

On the Correctness of Transactional Memory

From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement

FLeet: Online Federated Learning via Staleness Awareness and Performance Prediction

Efficient Distributed Subtyping Tests

Replication of CORBA Objects