@inproceedings{889d7d12210d469f8c7d9fd6dc17c29b,
title = "Asymptotically optimal distributed consensus: Extended abstract",
abstract = "The Distributed Consensus problem requires correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. In this paper we present a protocol that achieves consensus with n>4t total processors using 2t+2 rounds of communication and messages of size 1. This is the first protocol in which all three parameters are simultaneously within a constant factor from their optima. Subsequently, we modify it to obtain a family of equally resilient protocols which use t(1 + 1/d) rounds and O(2d) message size, improving on previous results. Finally, we show that the first protocol can be adapted very efficiently to run on bounded-degree networks, so that consensus can be reached in the presence of O(n/log n) faulty processors in time O(n). It improves on the previous result, which implied that consensus can be reached in this setting in time Θ(n3).",
author = "Piotr Berman and Garay, \{Juan A.\}",
note = "Publisher Copyright: {\textcopyright} 1989, Springer-Verlag.; 16th International Colloquium on Automata, Languages and Programming, 1989 ; Conference date: 11-07-1989 Through 15-07-1989",
year = "1989",
doi = "10.1007/BFb0035753",
language = "English (US)",
isbn = "9783540513711",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "80--94",
editor = "Mariangiola Dezani-Ciancaglini and \{Della Rocca\}, \{Simonetta Ronchi\} and Giorgio Ausiello",
booktitle = "Automata, Languages and Programming - 16th International Colloquium, Proceedings",
address = "Germany",
}