---
OA_type: closed access
_id: '773'
abstract:
- lang: eng
  text: "We describe a new randomized consensus protocol with expected message complexity
    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 Ω(n2) message lower bound. The protocol further ensures that no process
    sends more than O(n log3n) 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 + t2log2t) total messages. Our
    protocol uses messages of size O(log n), and can therefore scale to large networks.\r\n\r\nWe
    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.\r\n\r\nOur
    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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: James
  full_name: Aspnes, James
  last_name: Aspnes
- first_name: Valerie
  full_name: King, Valerie
  last_name: King
- first_name: Jared
  full_name: Saia, Jared
  last_name: Saia
citation:
  ama: 'Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized
    consensus. In: Kuhn F, ed. <i>28th International Symposium Distributed Computing
    2014</i>. Vol 8784. Springer; 2014:61-75. doi:<a href="https://doi.org/10.1007/978-3-662-45174-8_5">10.1007/978-3-662-45174-8_5</a>'
  apa: 'Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2014). Communication-efficient
    randomized consensus. In F. Kuhn (Ed.), <i>28th International Symposium Distributed
    Computing 2014</i> (Vol. 8784, pp. 61–75). Austin, TX, United States: Springer.
    <a href="https://doi.org/10.1007/978-3-662-45174-8_5">https://doi.org/10.1007/978-3-662-45174-8_5</a>'
  chicago: Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient
    Randomized Consensus.” In <i>28th International Symposium Distributed Computing
    2014</i>, edited by Fabian Kuhn, 8784:61–75. Springer, 2014. <a href="https://doi.org/10.1007/978-3-662-45174-8_5">https://doi.org/10.1007/978-3-662-45174-8_5</a>.
  ieee: D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient
    randomized consensus,” in <i>28th International Symposium Distributed Computing
    2014</i>, Austin, TX, United States, 2014, vol. 8784, pp. 61–75.
  ista: 'Alistarh D-A, Aspnes J, King V, Saia J. 2014. Communication-efficient randomized
    consensus. 28th International Symposium Distributed Computing 2014. DISC: Distributed
    Computing, LNCS, vol. 8784, 61–75.'
  mla: Alistarh, Dan-Adrian, et al. “Communication-Efficient Randomized Consensus.”
    <i>28th International Symposium Distributed Computing 2014</i>, edited by Fabian
    Kuhn, vol. 8784, Springer, 2014, pp. 61–75, doi:<a href="https://doi.org/10.1007/978-3-662-45174-8_5">10.1007/978-3-662-45174-8_5</a>.
  short: D.-A. Alistarh, J. Aspnes, V. King, J. Saia, in:, F. Kuhn (Ed.), 28th International
    Symposium Distributed Computing 2014, Springer, 2014, pp. 61–75.
conference:
  end_date: 2014-10-15
  location: Austin, TX, United States
  name: 'DISC: Distributed Computing'
  start_date: 2014-10-12
date_created: 2018-12-11T11:48:25Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2026-09-09T12:28:14Z
day: '01'
doi: 10.1007/978-3-662-45174-8_5
editor:
- first_name: Fabian
  full_name: Kuhn, Fabian
  last_name: Kuhn
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-662-45174-8_5
intvolume: '      8784'
language:
- iso: eng
month: '01'
oa_version: None
page: 61 - 75
publication: 28th International Symposium Distributed Computing 2014
publication_identifier:
  eisbn:
  - '9783662451748'
  isbn:
  - '9783662451731'
publication_status: published
publisher: Springer
publist_id: '6881'
status: public
title: Communication-efficient randomized consensus
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 8784
year: '2014'
...