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 this paper we tackle the challenge of making the stochastic coordinate descent algorithm differentially private. Compared to the classical gradient descent algorithm where updates operate on a single model vector and controlled noise addition to this ve ...

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

A method for aggregating digital signatures comprises the following steps carried out by a signature aggregator: receiving first data packages from signers, each first data package comprising a signer identifier, a payload, and a payload signature; verifyi ...

Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well- ...

This paper presents LiFTinG, the first protocol to detect freeriders, including colluding ones, in gossip-based content dissemination systems with asymmetric data exchanges. LiFTinG relies on nodes tracking abnormal behaviors by cross-checking the history of their previous interactions, and exploits the fact that nodes pick neighbors at random to prevent colluding nodes from covering up each others' bad actions.

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. They are also considered highly ﬂexible, namely tunable at will to increase their robustness and adapt to churn. So far however, the ...

Consider a set of players that are interested in collectively evaluating a set of objects. We develop a collaborative scori ng protocol in which each player evaluates a subset of the objects, after which we can accurately predict each players’ individual o ...

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

A universal construction is an algorithm which transforms any sequential implementation of an object into a concurrent implementation of that same object in a linearizable and wait-free manner. Such constructions require underlying low-level universal shar ...

In this work, we present transaction polymorphism; a synchronization technique that provides more control to the programmer than traditional (i.e., monomorphic) transactions to achieve comparable performance to generic lock-based and lock-free solutions. ...

We study erasure-coded atomic register implementations in an asynchronous crash-recovery model. Erasure coding provides a cheap and space-efficient way to tolerate failures in a distributed system. This paper presents ORCAS, Optimistic eRasure-Coded Atomic ...

We report on \emph{Krum}, the first \emph{provably} Byzantine-tolerant aggregation rule for distributed Stochastic Gradient Descent (SGD). Krum guarantees the convergence of SGD even in a distributed setting where (asymptotically) up to half of the workers ...

Composing software is notoriously difficult, especially when it is concurrent. Two fine-grained locked operations may for instance easily deadlock upon composition. One of the most appealing features of transactions is, on the other hand, that they compose. Indeed they do so, but only in their original, orthodox, form. As we discuss in the paper, as soon as we slightly relax the model to enable more concurrency, we incur the risk of breaking encapsulation.

Rachid Guerraoui

Chat with Graph Search

Differentially Private Stochastic Coordinate Descent

Fast Randomized Test-and-Set and Renaming

Rapidly verifiable aggregate signatures

On the Message Complexity of Indulgent Consensus

LiFTinG: Lightweight Freerider-Tracking in Gossip

Stretching Gossip with Live Streaming

The Utility and Privacy Effects of a Click

The consensus number of a cryptocurrency (vol 35, pg 1, 2022)

(Almost) All Objects are Universal in Message Passing Systems

Collaborative Scoring with Dishonest Participants

The Disagreement Power of an Adversary

A Thrifty Universal Construction

Flexible Task Graphs:Unified Restricted Thread Programming Model for Java

Brief Announcement: Transaction Polymorphism

The Road to a Universal Internet Machine

Special section with selected papers from PODC 2010

Model Checking Transactional Memories

Optimistic Erasure-Coded Distributed Storage

Brief Announcement: Byzantine-Tolerant Machine Learning

Composition vs Concurrency