License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.27
URN: urn:nbn:de:0030-drops-98167
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9816/
Go to the corresponding LIPIcs Volume Portal

Függer, Matthias ; Nowak, Thomas

Fast Multidimensional Asymptotic and Approximate Consensus

pdf-format:
LIPIcs-DISC-2018-27.pdf (0.5 MB)

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(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.

BibTeX - Entry

@InProceedings{fgger_et_al:LIPIcs:2018:9816,
  author =	{Matthias F{\"u}gger and Thomas Nowak},
  title =	{{Fast Multidimensional Asymptotic and Approximate Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9816},
  URN =		{urn:nbn:de:0030-drops-98167},
  doi =		{10.4230/LIPIcs.DISC.2018.27},
  annote =	{Keywords: asymptotic consensus, approximate consensus, multidimensional data, dynamic networks, Byzantine processes}
}

Keywords: asymptotic consensus, approximate consensus, multidimensional data, dynamic networks, Byzantine processes
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI