Last update: Sun Mar 31 02:13:37 MDT 2019
@Article{Correia:2006:CAB,
author = "Miguel Correia and Nuno Ferreira Neves and Paulo
Ver{\'\i}ssimo",
title = "From Consensus to Atomic Broadcast: Time-Free
{Byzantine}-Resistant Protocols without Signatures",
journal = j-COMP-J,
volume = "49",
number = "1",
pages = "82--96",
month = jan,
year = "2006",
CODEN = "CMPJA6",
DOI = "https://doi.org/10.1093/comjnl/bxh145",
ISSN = "0010-4620 (print), 1460-2067 (electronic)",
ISSN-L = "0010-4620",
bibdate = "Wed Dec 21 17:38:55 MST 2005",
bibsource = "http://comjnl.oxfordjournals.org/content/vol49/issue1/index.dtl;
http://www.math.utah.edu/pub/tex/bib/compj2000.bib",
URL = "http://comjnl.oxfordjournals.org/cgi/content/abstract/49/1/82;
http://comjnl.oxfordjournals.org/cgi/content/full/49/1/82;
http://comjnl.oxfordjournals.org/cgi/reprint/49/1/82",
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 =
\lfloor(n-1)/3\rfloor$ 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.",
acknowledgement = ack-nhfb,
fjournal = "The Computer Journal",
journal-URL = "http://comjnl.oxfordjournals.org/",
}