Approximate consensus in highly dynamic networks: the role of averaging algorithms
From MaRDI portal
Publication:3449502
DOI10.1007/978-3-662-47666-6_42zbMATH Open1417.68012arXiv1408.0620OpenAlexW2152755966MaRDI QIDQ3449502FDOQ3449502
Authors: Bernadette Charron-Bost, Matthias Függer, Thomas Nowak 
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 in a coordinated network model in synchronous rounds, and in rounds when the maximum round delay for a message to be delivered is . 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
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 (preliminary version)
- 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 (35)
- 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
- Order-Optimal Consensus Through Randomized Path Averaging
- Derivation of heard-of predicates from elementary behavioral patterns
- An improved approximate consensus algorithm in the presence of mobile faults
- Title not available (Why is that?)
- Maximizing convergence time in network averaging dynamics subject to edge removal
- Consensus and influence power approximation in time‐varying and directed networks subject to perturbations
- Tight Bounds for Asymptotic and Approximate Consensus
- Coordinated consensus in dynamic networks
- Reaching approximate Byzantine consensus with multi-hop communication
- A characterization of dynamic networks where consensus is solvable
- Consensus in rooted dynamic networks with short-lived stability
- Approximate agreement under mobile Byzantine faults
- Fast, robust, quantizable approximate consensus
- Iterative approximate Byzantine consensus in arbitrary directed graphs
- Extension of PID regulators to dynamical systems on smooth manifolds (M-PID)
- Fast multidimensional asymptotic and approximate consensus
- Fast consensus in networks of bounded degree.
- Minimal control effort and time Lie-group synchronisation design based on proportional-derivative control
- Tight bounds for asymptotic and approximate consensus
- Dynamic average consensus via nonlinear protocols
- 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
- A connectivity model for agreement in dynamic systems
- 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)
