Miguel Correia, Nuno F.
Neves, Paulo Veríssimo
Computer Journal. vol. 41, n. 1, pp 82-96, January 2006.
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.
@ARTICLE{Correia:06a,
author = {M. Correia and N. F. Neves and P. Ver\'{\i}ssimo},
title = {From Consensus to Atomic Broadcast:
Time-Free Byzantine-Resistant Protocols without Signatures},
journal = {Computer Journal},
year = {2006},
volume = {41},
number = {1},
pages = {82--96},
month = {Jan}
}
Download the pdf.