Paper Info
Title
Fast Multidimensional Asymptotic and Approximate Consensus.
Abstract
We study the problems of asymptotic and approximate consensus in which agents have to get their values arbitrarily close to each othersu0027 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 agentsu0027 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(d log (d Delta)/epsilon) to O(log Delta/epsilon), where Delta is the initial and epsilon is the terminal diameter of the set of vectors of correct agents.
Year
DOI
Venue
2018
10.4230/LIPIcs.DISC.2018.27
DISC
DocType
Volume
Citations 
Conference
abs/1805.04923
0
PageRank 
References 
Authors
0.34
13
2
Name
Order
Citations
PageRank
Matthias Függer116721.14
Thomas Nowak2329.18