---
_id: '3422'
abstract:
- lang: eng
  text: "We study the consensus problem in a synchronous distributed system of n nodes
    under an adaptive adversary that has a slightly outdated view of the system and
    can block all incoming and outgoing communication of a constant fraction of the
    nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing
    that any consensus algorithm that is resilient against a linear number of crash
    faults requires $\\tilde \\Omega(\\sqrt n)$ rounds in an n-node network against
    an adaptive adversary, we consider a late adaptive adversary, who has full knowledge
    of the network state at the beginning of the previous round and unlimited computational
    power, but is oblivious to the current state of the nodes. \r\n\r\nOur main contributions
    are randomized distributed algorithms that achieve consensus with high probability
    among all except a small constant fraction of the nodes (i.e., \"almost-everywhere'')
    against a late adaptive adversary who can block up to ε n$ nodes in each round,
    for a small constant ε >0$. Our first protocol achieves binary almost-everywhere
    consensus and also guarantees a decision on the majority input value, thus ensuring
    plurality consensus. We also present an algorithm that achieves the same time
    complexity for multi-value consensus. Both of our algorithms succeed in $O(log
    n)$ rounds with high probability, thus showing an exponential gap to the $\\tilde\\Omega(\\sqrt
    n)$ lower bound of Ben-Or and Bar-Joseph for strongly adaptive crash-failure adversaries,
    which can be strengthened to $\\Omega(n)$ when allowing the adversary to block
    nodes instead of permanently crashing them. Our algorithms are scalable to large
    systems as each node contacts only an (amortized) constant number of peers in
    each communication round. We show that our algorithms are optimal up to constant
    (resp.\\ sub-logarithmic) factors by proving that every almost-everywhere consensus
    protocol takes $\\Omega(log_d n)$ rounds in the worst case, where d is an upper
    bound on the number of communication requests initiated per node in each round.
    We complement our theoretical results with an experimental evaluation of the binary
    almost-everywhere consensus protocol revealing a short convergence time even against
    an adversary blocking a large fraction of nodes."
author:
- first_name: Peter
  full_name: Robinson, Peter
  last_name: Robinson
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Robinson P, Scheideler C, Setzer A. Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary. In: <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. doi:<a
    href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>'
  apa: 'Robinson, P., Scheideler, C., &#38; Setzer, A. (n.d.). Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary. In <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. Wien.
    <a href="https://doi.org/10.1145/3210377.3210399">https://doi.org/10.1145/3210377.3210399</a>'
  bibtex: '@inproceedings{Robinson_Scheideler_Setzer, title={Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary}, DOI={<a href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>},
    booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, author={Robinson, Peter and Scheideler, Christian and
    Setzer, Alexander} }'
  chicago: 'Robinson, Peter, Christian Scheideler, and Alexander Setzer. “Breaking
    the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.”
    In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA)</i>, n.d. <a href="https://doi.org/10.1145/3210377.3210399">https://doi.org/10.1145/3210377.3210399</a>.'
  ieee: 'P. Robinson, C. Scheideler, and A. Setzer, “Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary,” in <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, Wien.'
  mla: 'Robinson, Peter, et al. “Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast
    Consensus under a Late Adversary.” <i>Proceedings of the 30th ACM Symposium on
    Parallelism in Algorithms and Architectures (SPAA)</i>, doi:<a href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>.'
  short: 'P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA), n.d.'
conference:
  end_date: 2018-07-18
  location: Wien
  name: 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  start_date: 2018-07-16
date_created: 2018-07-04T08:55:45Z
date_updated: 2022-01-06T06:59:16Z
ddc:
- '040'
department:
- _id: '79'
- _id: '34'
- _id: '7'
doi: 10.1145/3210377.3210399
file:
- access_level: closed
  content_type: application/pdf
  creator: asetzer
  date_created: 2018-10-31T13:30:40Z
  date_updated: 2018-10-31T13:30:40Z
  file_id: '5215'
  file_name: p173-robinson.pdf
  file_size: 1675407
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T13:30:40Z
has_accepted_license: '1'
keyword:
- distributed consensus
- randomized algorithm
- adaptive adversary
- complexity lower bound
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
publication: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
publication_identifier:
  isbn:
  - 978-1-4503-5799-9/18/07
publication_status: accepted
status: public
title: 'Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late
  Adversary'
type: conference
user_id: '11108'
year: '2018'
...