Distributed agreement with optimal communication complexity
Distributed agreement with optimal communication complexity
复制标题
具有最佳通信复杂度的分布式协议
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Kowalski
中科院分区：
文献类型：
--
作者：
Seth Gilbert;D. Kowalski
研究易崩溃同步系统中的容错协议问题。我们提出了一种新的随机共识算法，该算法实现了最优的通信效率，仅使用O(n)位通信，并以高概率在（几乎最优）时间O（log n）内终止。同样的协议，稍加修改，也可以用于部分同步网络，即使在异步执行中也能保证正确的行为，同时在同步执行中保持高效的性能。最后，同样的技术还产生了一个随机的、容错的八卦协议，它使用O(n)条消息在O（log* n）轮中终止（其位复杂度取决于被八卦的数据）。
We consider the problem of fault-tolerant agreement in a crash-prone synchronous system. We present a new randomized consensus algorithm that achieves optimal communication efficiency, using only O(n) bits of communication, and terminates in (almost optimal) time O(log n), with high probability. The same protocol, with minor modifications, can also be used in partially synchronous networks, guaranteeing correct behavior even in asynchronous executions, while maintaining efficient performance in synchronous executions. Finally, the same techniques also yield a randomized, fault-tolerant gossip protocol that terminates in O(log* n) rounds using O(n) messages (with bit complexity that depends on the data being gossiped).