Distributed Agreement with Optimal Communication Complexity

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(logn), 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).


Publié dans:
Proceedings Of The Twenty-First Annual Acm-Siam Symposium On Discrete Algorithms, 135, 965-977
Présenté à:
21st Annual ACM/SIAM Symposium on Discrete Algorithms, Austin, TX, Jan 17-19, 2010
Année
2010
Publisher:
Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa
ISBN:
978-0-898717-01-3
Mots-clefs:
Laboratoires:




 Notice créée le 2011-12-16, modifiée le 2019-12-05


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)