Fast multidimensional asymptotic and approximate consensus

DOI10.4230/LIPICS.DISC.2018.27zbMATH Open1497.68045arXiv1805.04923OpenAlexW2963922292MaRDI QIDQ5090919FDOQ5090919

Authors: Matthias Függer, Thomas Nowak 

Publication date: 21 July 2022

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Stability of multiagent systems with time-dependent communication links
• The total \(s\)-energy of a multiagent system
• 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: Convergence Rates, Measurement Delays, and Asynchronous Events
• Stability of leaderless discrete-time multi-agent systems
• The Heard-Of model: computing in distributed systems with benign faults
• Reaching approximate agreement in the presence of faults
• Optimal Byzantine-resilient convergence in uni-dimensional robot networks
• Time is not a healer (preliminary version)
• Approximating the centroid is hard
• A new fault-tolerant algorithm for clock synchronization
• Principles of Distributed Systems
• Multidimensional agreement in Byzantine systems
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Tight bounds for asymptotic and approximate consensus
• Fast, robust, quantizable approximate consensus

Cited In (9)

• 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
• 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)