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.2019.29
URN: urn:nbn:de:0030-drops-113363
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11336/
Go to the corresponding LIPIcs Volume Portal

Nowak, Thomas ; Rybicki, Joel

Byzantine Approximate Agreement on Graphs

pdf-format:
LIPIcs-DISC-2019-29.pdf (0.6 MB)

Abstract

Consider a distributed system with n processors out of which f can be Byzantine faulty. In the approximate agreement task, each processor i receives an input value x_i and has to decide on an output value y_i such that
1) the output values are in the convex hull of the non-faulty processors' input values,
2) the output values are within distance d of each other.
Classically, the values are assumed to be from an m-dimensional Euclidean space, where m >= 1.
In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to output vertices that are within distance d of each other in G, but still remain in the graph-induced convex hull of the input values. For d=0, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any d >= 1, we show that the task is solvable in asynchronous systems when G is chordal and n > (omega+1)f, where omega is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.

BibTeX - Entry

@InProceedings{nowak_et_al:LIPIcs:2019:11336,
  author =	{Thomas Nowak and Joel Rybicki},
  title =	{{Byzantine Approximate Agreement on Graphs}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11336},
  URN =		{urn:nbn:de:0030-drops-113363},
  doi =		{10.4230/LIPIcs.DISC.2019.29},
  annote =	{Keywords: consensus, approximate agreement, Byzantine faults, chordal graphs, lattice agreement}
}

Keywords: consensus, approximate agreement, Byzantine faults, chordal graphs, lattice agreement
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

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