Dan Alistarh, James Aspnes, Valerie King, and Jared Saia. Communication-efficient randomized consensus. Distributed Computing, 31(6):489–501, November 2018. An earlier version appeared in Distributed Computing — 28th International Symposium, DISC 2014, Austin, TX, USA, October 12–15, 2014. Proceedings, Lecture Notes in Computer Science 8784, Springer, October 2014, pp. 61–75.
We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.
We describe a new randomized consensus protocol with expected message complexity O(n² log² n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n²) message lower bound. The protocol further ensures that no process sends more than O(n log³ n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t² log² t) total messages.
Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing a message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.
@Article{AlistarhAKS2018,
author="Alistarh, Dan
and Aspnes, James
and King, Valerie
and Saia, Jared",
title="Communication-efficient randomized consensus",
journal="Distributed Computing",
year="2018",
month="Nov",
day="01",
volume="31",
number="6",
pages="489--501",
abstract="We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity {\$}{\$}O( n^2 {\backslash}log ^2 n ){\$}{\$}O(n2log2n)when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known {\$}{\$}{\backslash}Omega ( n^2 ){\$}{\$}$\Omega$(n2)message lower bound. The protocol further ensures that no process sends more than {\$}{\$}O( n {\backslash}log ^3 n ){\$}{\$}O(nlog3n)messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected {\$}{\$}O( n t + t^2 {\backslash}log ^{\{}2{\}} t ){\$}{\$}O(nt+t2log2t)total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still ``in flight'' (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.",
issn="1432-0452",
doi="10.1007/s00446-017-0315-1",
url="https://doi.org/10.1007/s00446-017-0315-1"
}