Publication
As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!
Publications associées (36)
Planetary-Scale Byzantine Fault Tolerance
The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...
EPFL2024Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!
Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira, Vincent Gramoli, Seth Gilbert
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 ...
2023As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!
Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert
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 SCIENCE2023Leaderless consensus
Rachid Guerraoui, Gauthier Jérôme Timothée Voron, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, Antoine Philippe Matthieu Desjardins
Classic synchronous consensus algorithms are leaderless in that processes exchange proposals, choose the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are typically leader-based. Although t ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2023Communication Complexity of Collision
Mika Tapani Göös, Siddhartha Jain
The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...
Leibniz-Zentrum für Informatik2022Minimum Cost Intervention Design for Causal Effect Identification
Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami
Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...
PMLR2022Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira, Vincent Gramoli, Seth Gilbert
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 Publishing2022Rational Agreement in the Presence of Crash Faults
Vincent Gramoli, Alejandro Ranchal Pedrosa
Blockchain systems need to solve consensus despite the presence of rational users and failures. The notion of (k, t)-robustness is key to derive impossibility results with k rational players and t faulty players. However, these t faulty players are always ...
IEEE2021Cooperative Data Exchange and Private Information Retrieval
Coding techniques have been well studied and used for improving communication quality by combating noise and mitigating interference.
Recently, it has been shown that the same coding techniques can also be exploited to further improve communication perform ...
EPFL2020Scalable Byzantine Reliable Broadcast
Rachid Guerraoui, Dragos-Adrian Seredinschi, Matej Pavlovic, Matteo Monti
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 ...
Schloss Dagstuhl--Leibniz-Zentrum fer Informatik2019