Publication
Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
Related publications (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 ...
2023Building Strongly-Consistent Systems Resilient to Failures, Partitions, and Slowdowns
Distributed systems designers typically strive to improve performance and preserve availability despite failures or attacks; but, when strong consistency is also needed, they encounter fundamental limitations. The bottleneck is in replica coordination, whi ...
EPFL2023As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!
Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert
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 ...
IEEE2022Asynchronous distributed coordination and consensus with threshold logical clocks
Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. The invention proposes an approach to simplify asynchronous consensus by building it atop a novel threshold logic ...
2021Leaderless Consensus
Rachid Guerraoui, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, Antoine Philippe Matthieu Desjardins
Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, retain the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are more robust in that they only req ...
IEEE COMPUTER SOC2021Rational 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 ...
IEEE2021The Performance of Byzantine Fault Tolerant Blockchains
Blockchains have captured the attention of many, resulting in an abundance of new systems available for use. However, selecting an appropriate blockchain for an application is challenging due to the lack of comparative information discussing core metrics s ...
IEEE2020Mneme: A Mobile Distributed Ledger
Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos
Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need ...
IEEE2020Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and Threshold Logical Clocks
Bryan Alexander Ford, Philipp Svetolik Jovanovic
It is commonly held that asynchronous consensus is much more complex, difficult, and costly than partially-synchronous algorithms, especially without using common coins. This paper challenges that conventional wisdom with que sera consensus QSC, an approac ...
2020