Approximate consensus in highly dynamic networks: the role of averaging algorithms

DOI10.1007/978-3-662-47666-6_42zbMATH Open1417.68012arXiv1408.0620OpenAlexW2152755966MaRDI QIDQ3449502FDOQ3449502

Thomas Nowak, Matthias Függer, Bernadette Charron-Bost

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: In this paper, we investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous systems, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree, i.e., there is a coordinator at each time. The striking point in this result is that the coordinator is not required to be unique and can change arbitrarily from round to round. Interestingly, the class of averaging algorithms, which are memoryless and require no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm. Concerning the time complexity of averaging algorithms, we show that approximate consensus can be achieved with precision of $varepsilon$ in a coordinated network model in $O(n^{n+1}logfrac1varepsilon)$ synchronous rounds, and in $O(Delta{n}^{nDelta+1}logfrac1varepsilon)$ rounds when the maximum round delay for a message to be delivered is $Delta$. While in general, an upper bound on the time complexity of averaging algorithms has to be exponential, we investigate various network models in which this exponential bound in the number of nodes reduces to a polynomial bound. We apply our results to networked systems with a fixed topology and classical benign fault models, and deduce both known and new results for approximate consensus in these systems. In particular, we show that for solving approximate consensus, a complete network can tolerate up to 2n-3 arbitrarily located link faults at every round, in contrast with the impossibility result established by Santoro and Widmayer (STACS '89) showing that exact consensus is not solvable with n-1 link faults per round originating from the same node.

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

Recommendations

• Fast, robust, quantizable approximate consensus
• Tight bounds for asymptotic and approximate consensus
• Tight Bounds for Asymptotic and Approximate Consensus
• Fast multidimensional asymptotic and approximate consensus
• Convergence speed in distributed consensus and averaging

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
• Distributed computation in dynamic networks
• Impossibility of distributed consensus with one faulty process
• Are wait-free algorithms fast?
• Sets of matrices all infinite products of which converge
• Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events
• The Heard-Of model: computing in distributed systems with benign faults
• Reaching approximate agreement in the presence of faults
• Coordinated consensus in dynamic networks
• Time is not a healer
• How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-Hard
• A Characterization of Dynamic Networks Where Consensus Is Solvable
• Degree Fluctuations and the Convergence Time of Consensus Algorithms

Cited In (28)

• Tutorial on Dynamic Average Consensus: The Problem, Its Applications, and the Algorithms
• A topological perspective on distributed network algorithms
• On linear-time data dissemination in dynamic rooted trees
• Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
• Synthesis in presence of dynamic links
• Fast Multidimensional Asymptotic and Approximate Consensus
• Order-Optimal Consensus Through Randomized Path Averaging
• Title not available (Why is that?)
• Consensus and influence power approximation in time‐varying and directed networks subject to perturbations
• Tight Bounds for Asymptotic and Approximate Consensus
• Extension of PID Regulators to Dynamical Systems on Smooth Manifolds (M-PID)
• Consensus in rooted dynamic networks with short-lived stability
• Approximate agreement under mobile Byzantine faults
• Iterative approximate Byzantine consensus in arbitrary directed graphs
• Fast consensus in networks of bounded degree.
• Minimal control effort and time Lie-group synchronisation design based on proportional-derivative control
• Packet efficient implementation of the Omega failure detector
• Dynamic average consensus via nonlinear protocols
• Derivation of Heard-of Predicates from Elementary Behavioral Patterns
• Title not available (Why is that?)
• On the radius of nonsplit graphs and information dissemination in dynamic networks
• Round-Oblivious Stabilizing Consensus in Dynamic Networks
• Average-Consensus in a Deterministic Framework— Part II: Central Connectivity
• Title not available (Why is that?)
• Fast consensus seeking on networks with antagonistic interactions
• The time complexity of consensus under oblivious message adversaries
• MinMax algorithms for stabilizing consensus
• Approximate consensus in the dynamic stochastic network with incomplete information and measurement delays

This page was built for publication: Approximate consensus in highly dynamic networks: the role of averaging algorithms

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