Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary
accepted
Peter
Robinson
author
Christian
Scheideler
author 20792
Alexander
Setzer
author 11108
79
department
34
department
7
department
30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
SFB 901
project
SFB 901 - Project Area C
project
SFB 901 - Subproject C1
project
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.
Our 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.
/download/3422/5215/p173-robinson.pdf
application/pdf
2018Wien
eng
distributed consensusrandomized algorithmadaptive adversarycomplexity lower bound
Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
978-1-4503-5799-9/18/0710.1145/3210377.3210399
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>.
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>
Robinson, P., Scheideler, C., & 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>
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.
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>.
P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), n.d.
@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} }
34222018-07-04T08:55:45Z2019-01-03T13:14:27Z