Publications de Seth Gilbert | EPFL Graph Search

All Byzantine Agreement Problems Are Expensive

Rachid Guerraoui, Seth Gilbert, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

Byzantine agreement, arguably the most fundamental problem in distributed computing, operates among n processes, out of which t < n can exhibit arbitrary failures. The problem states that all correct (non-faulty) processes must eventually decide (terminati ...

ACM2024

DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication

Rachid Guerraoui, Seth Gilbert, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

Byzantine Agreement (BA) enables n processes to reach consensus on a common valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from their prescribed protocol. Despite its significance, the optimal communic ...

ACM2024

On the Validity of Consensus

Rachid Guerraoui, Seth Gilbert, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement ...

Assoc Computing Machinery2023

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Rachid Guerraoui, Seth Gilbert, Vincent Gramoli, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

2023

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

Rachid Guerraoui, Seth Gilbert, Vincent Gramoli, Jovan Komatovic, Pierre Philippe Civit

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

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

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

Rachid Guerraoui, Seth Gilbert, Vincent Gramoli, Jovan Komatovic, Pierre Philippe Civit

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

IEEE2022

Crime and Punishment in Distributed Byzantine Decision Tasks

Rachid Guerraoui, Zarko Milosevic, Seth Gilbert, Vincent Gramoli, Jovan Komatovic, Pierre Philippe Civit

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. ...

IEEE COMPUTER SOC2022

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Rachid Guerraoui, Seth Gilbert, Vincent Gramoli, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether ...

Dagstuhl Publishing2022

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

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

Association for Computing Machinery2014

Asynchronous Gossip

Rachid Guerraoui, Seth Gilbert

We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. The algorithmic techniques prop ...

Association for Computing Machinery2013

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

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

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

2012

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

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

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

2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key buildi ...

IEEE2012

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer Verlag2012

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Hagit Albo Attiya, Seth Gilbert, Dan Alistarh, Andrei Giurgiu

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

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Securing Every Bit: Authenticated Broadcast in Radio Networks

Rachid Guerraoui, Zarko Milosevic, Seth Gilbert, Dan Alistarh

This paper studies non-cryptographic authenticated broad- cast in radio networks subject to malicious failures. We in- troduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monito ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

Collaborative Scoring with Dishonest Participants

Rachid Guerraoui, Seth Gilbert, Faezeh Malakouti

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

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010