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.68012OpenAlexW2152755966MaRDI QIDQ3449502FDOQ3449502
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.
Recommendations
Cites Work
- scientific article; zbMATH DE number 996442 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A characterization of dynamic networks where consensus is solvable
- Are wait-free algorithms fast?
- Coordinated consensus in dynamic networks
- Degree Fluctuations and the Convergence Time of Consensus Algorithms
- Distributed computation in dynamic networks
- How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard
- Impossibility of distributed consensus with one faulty process
- Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
- Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events
- Reaching approximate agreement in the presence of faults
- Sets of matrices all infinite products of which converge
- The Heard-Of model: computing in distributed systems with benign faults
- Time is not a healer (preliminary version)
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 no real title available?)
- 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 no real title available?)
- 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 no real title available?)
- 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)
