---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Peter
foaf_name: Robinson, Peter
foaf_surname: Robinson
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Setzer, Alexander
foaf_surname: Setzer
foaf_workInfoHomepage: http://www.librecat.org/personId=11108
bibo_doi: 10.1145/3210377.3210399
dct_date: 2018^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-1-4503-5799-9/18/07
dct_language: eng
dct_subject:
- distributed consensus
- randomized algorithm
- adaptive adversary
- complexity lower bound
dct_title: 'Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under
a Late Adversary@'
...