Tight bounds for asymptotic and approximate consensus

DOI10.1145/3212734.3212762zbMATH Open1428.68067arXiv1705.02898OpenAlexW2810645111MaRDI QIDQ5197697FDOQ5197697

Authors: Matthias Függer, Thomas Nowak, Manfred Schwarz 

Publication date: 19 September 2019

Published in: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We study the performance of asymptotic and approximate consensus algorithms under harsh environmental conditions. The asymptotic consensus problem requires a set of agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values. This problem, and the related approximate consensus problem, are fundamental building blocks in distributed systems where exact consensus among agents is not required or possible, e.g., man-made distributed control systems, and have applications in the analysis of natural distributed systems, such as flocking and opinion dynamics. We prove tight lower bounds on the contraction rates of asymptotic consensus algorithms in dynamic networks, from which we deduce bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented in [Charron-Bost et al., ICALP'16] for certain dynamic networks, including the weakest dynamic network model in which asymptotic and approximate consensus are solvable. As a corollary we also obtain asymptotically tight bounds for asymptotic consensus in the classical asynchronous model with crashes. Central to our lower bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.

Full work available at URL: https://arxiv.org/abs/1705.02898

Recommendations

• Tight Bounds for Asymptotic and Approximate Consensus
• Fast multidimensional asymptotic and approximate consensus
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Fast, robust, quantizable approximate consensus
• Lower bounds for asynchronous consensus

zbMATH Keywords

dynamic networkslower boundsasymptotic consensusapproximate consensus

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (11)

• A topological perspective on distributed network algorithms
• Fast Multidimensional Asymptotic and Approximate Consensus
• Tight Bounds for Asymptotic and Approximate Consensus
• Coordinated consensus in dynamic networks
• An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
• Distributed Computing
• Fast, robust, quantizable approximate consensus
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Wait-free approximate agreement on graphs
• The time complexity of consensus under oblivious message adversaries
• Cutoff bounds for consensus algorithms

This page was built for publication: Tight bounds for asymptotic and approximate consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197697)