Asynchronous Byzantine consensus with 2f+1 processes
- 22 March 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 475-480
- https://doi.org/10.1145/1774088.1774187
Abstract
Byzantine consensus in asynchronous message-passing systems has been shown to require at least 3f + 1 processes to be solvable in several system models (e.g., with failure detectors, partial synchrony or randomization). Recently a couple of solutions to implement Byzantine fault-tolerant state-machine replication using only 2f + 1 replicas have appeared. This reduction from 3f + 1 to 2f + 1 is possible with a hybrid system model, i.e., by extending the system model with trusted/trustworthy components that constrain the power of faulty processes to have certain behaviors. Despite these important results, the problem of solving Byzantine consensus with only 2f + 1 processes is still far from being well understood. In this paper we present a methodology to transform crash consensus algorithms into Byzantine consensus algorithms with different characteristics, with the assistance of a reliable broadcast primitive that requires trusted/trustworthy components to be implemented. We exemplify the methodology with two algorithms, one that uses failure detectors and one that is randomized. We also define a new flavor of consensus and use it to solve atomic broadcast, showing the practical interest of the transformations.Keywords
Funding Information
- Fundação para a Ciência e a Tecnologia (PTDC/EIA-EIA/100581/2008 (REGENESYS)PTDC/EIA-EIA/100894/2008 (DIVERSE))
- European Commission (E05D057126BR)
This publication has 16 references indexed in Scilit:
- Travelling through wormholesACM SIGACT News, 2006
- From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without SignaturesThe Computer Journal, 2005
- Asynchronous bounded lifetime failure detectorsInformation Processing Letters, 2005
- Consensus in Byzantine asynchronous systemsJournal of Discrete Algorithms, 2003
- The generic consensus serviceIEEE Transactions on Software Engineering, 2001
- Indulgent algorithms (preliminary version)Published by Association for Computing Machinery (ACM) ,2000
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- A compiler that increases the fault tolerance of asynchronous protocolsIEEE Transactions on Computers, 1988
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985