---
_id: '536'
abstract:
- lang: eng
  text: '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(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(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(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.'
article_processing_charge: Yes (via OA deal)
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. <i>Distributed Computing</i>. 2018;31(6):489-501. doi:<a href="https://doi.org/10.1007/s00446-017-0315-1">10.1007/s00446-017-0315-1</a>
  apa: Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2018). Communication-efficient
    randomized consensus. <i>Distributed Computing</i>. Springer. <a href="https://doi.org/10.1007/s00446-017-0315-1">https://doi.org/10.1007/s00446-017-0315-1</a>
  chicago: Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient
    Randomized Consensus.” <i>Distributed Computing</i>. Springer, 2018. <a href="https://doi.org/10.1007/s00446-017-0315-1">https://doi.org/10.1007/s00446-017-0315-1</a>.
  ieee: D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient
    randomized consensus,” <i>Distributed Computing</i>, vol. 31, no. 6. Springer,
    pp. 489–501, 2018.
  ista: Alistarh D-A, Aspnes J, King V, Saia J. 2018. Communication-efficient randomized
    consensus. Distributed Computing. 31(6), 489–501.
  mla: Alistarh, Dan-Adrian, et al. “Communication-Efficient Randomized Consensus.”
    <i>Distributed Computing</i>, vol. 31, no. 6, Springer, 2018, pp. 489–501, doi:<a
    href="https://doi.org/10.1007/s00446-017-0315-1">10.1007/s00446-017-0315-1</a>.
  short: D.-A. Alistarh, J. Aspnes, V. King, J. Saia, Distributed Computing 31 (2018)
    489–501.
date_created: 2018-12-11T11:47:01Z
date_published: 2018-11-01T00:00:00Z
date_updated: 2023-02-23T12:23:25Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-017-0315-1
file:
- access_level: open_access
  checksum: 69b46e537acdcac745237ddb853fcbb5
  content_type: application/pdf
  creator: dernst
  date_created: 2019-01-22T07:25:51Z
  date_updated: 2020-07-14T12:46:38Z
  file_id: '5867'
  file_name: 2017_DistribComp_Alistarh.pdf
  file_size: 595707
  relation: main_file
file_date_updated: 2020-07-14T12:46:38Z
has_accepted_license: '1'
intvolume: '        31'
issue: '6'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 489-501
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Distributed Computing
publication_identifier:
  issn:
  - '01782770'
publication_status: published
publisher: Springer
publist_id: '7281'
quality_controlled: '1'
scopus_import: 1
status: public
title: Communication-efficient randomized consensus
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2018'
...