From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures
- 16 November 2005
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 49 (1), 82-96
- https://doi.org/10.1093/comjnl/bxh145
Abstract
This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ⌊(n−1)/3⌋ out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems.Keywords
This publication has 35 references indexed in Scilit:
- Low complexity Byzantine-resilient consensusDistributed Computing, 2005
- Total order broadcast and multicast algorithmsACM Computing Surveys, 2004
- Resilient-optimal interactive consistency in constant timeDistributed Computing, 2003
- Conditions on input vectors for consensus solvability in asynchronous distributed systemsJournal of the ACM, 2003
- Byzantine Fault Detectors for Solving ConsensusThe Computer Journal, 2003
- The SecureRing group communication systemACM Transactions on Information and System Security, 2001
- The generic consensus serviceIEEE Transactions on Software Engineering, 2001
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Asynchronous consensus and broadcast protocolsJournal of the ACM, 1985