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 nonfaulty processors' input values,
2) the output values are within distance d of each other.
Classically, the values are assumed to be from an mdimensional 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 graphinduced 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 Byzantinetolerant 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:129:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11336},
URN = {urn:nbn:de:0030drops113363},
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 