Fast multidimensional asymptotic and approximate consensus

DOI10.4230/LIPICS.DISC.2018.27MaRDI QIDQ5090919zbMATH OpenOpenAlexFDO

Authors Matthias Függer, Thomas Nowak

Publication date 21 July 2022

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

zbMATH Keywords

dynamic networksmultidimensional dataByzantine processesasymptotic consensusapproximate consensus

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We study the problems of asymptotic and approximate consensus in which agents have to get their values arbitrarily close to each others' inside the convex hull of initial values, either without or with an explicit decision by the agents. In particular, we are concerned with the case of multidimensional data, i.e., the agents' values are $d$-dimensional vectors. We introduce two new algorithms for dynamic networks, subsuming classical failure models like asynchronous message passing systems with Byzantine agents. The algorithms are the first to have a contraction rate and time complexity independent of the dimension $d$. In particular, we improve the time complexity from the previously fastest approximate consensus algorithm in asynchronous message passing systems with Byzantine faults by Mendes et al. [Distrib. Comput. 28] from $Omega!left(dlogfracdDeltavarepsilonight)$ to $O!left(logfracDeltavarepsilonight)$, where $Delta$ is the initial and $varepsilon$ is the terminal diameter of the set of vectors of correct agents.

Recommendations

• Multidimensional agreement in Byzantine systems
• Tight Bounds for Asymptotic and Approximate Consensus
• Tight bounds for asymptotic and approximate consensus
• Multidimensional approximate agreement in Byzantine asynchronous systems
• Fast, robust, quantizable approximate consensus

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 2038783 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• A new fault-tolerant algorithm for clock synchronization
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Approximating the centroid is hard
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Fast, robust, quantizable approximate consensus
• Multidimensional agreement in Byzantine systems
• Optimal Byzantine-resilient convergence in uni-dimensional robot networks
• Principles of Distributed Systems
• Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events
• Reaching approximate agreement in the presence of faults
• Stability of leaderless discrete-time multi-agent systems
• Stability of multiagent systems with time-dependent communication links
• The Heard-Of model: computing in distributed systems with benign faults
• The total \(s\)-energy of a multiagent system
• Tight bounds for asymptotic and approximate consensus
• Time is not a healer (preliminary version)

Cited in

(10)

• Multidimensional approximate agreement in Byzantine asynchronous systems
• Tight Bounds for Asymptotic and Approximate Consensus
• Fast Algorithms for Geometric Consensuses
• Fast, robust, quantizable approximate consensus
• Asynchronous fully-decentralized SGD in the cluster-based model
• Relaxed Byzantine vector consensus
• Tight bounds for asymptotic and approximate consensus
• Asynchronous convex hull consensus in the presence of crash faults
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Wait-free approximate agreement on graphs

This page was built for publication: Fast multidimensional asymptotic and approximate consensus

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