From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures
From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures
复制标题
从共识到原子广播：无需签名的无时间拜占庭抵抗协议
DOI：
10.1093/comjnl/bxh145
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Veríssimo
中科院分区：
文献类型：
--
作者：
M. Correia;N. Neves;P. Veríssimo
本文提出了一个堆栈的拜占庭抵抗协议，旨在用于实际的分布式系统：多值共识，向量共识和原子广播。这些协议被设计为从一个到另一个的连续转换。第一个协议，多值共识，是在一个随机化的二进制共识和一个可靠的广播协议之上实现的。这些协议共享一组重要的结构属性。首先，它们不使用用公钥密码构造的数字签名，这是这类协议中众所周知的性能瓶颈。其次，它们是无时间限制的，即它们不做同步假设，因为这些假设往往容易受到微妙但有效的攻击。第三，它们是完全分散的，从而避免了发现腐败领导人的成本。第四，它们具有最优的弹性，也就是说，它们可以容忍总共n个进程中f = n（n-1）/3 n的失败。在时间复杂度方面，多值共识协议终止于恒定的预期轮数，而向量共识和原子广播协议具有O（f）复杂度。证明了在无签名的拜占庭故障模型中多值一致性与原子广播的等价性。对多值一致性和向量一致性之间的等价性给出了类似的证明。这两个结果具有理论相关性，因为它们再次表明，共识是分布式系统中的一个基本问题。
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.