10.4230/LIPICS.DISC.2019.29
Nowak, Thomas
Thomas
Nowak
Rybicki, Joel
Joel
Rybicki0000-0002-6432-6646
Byzantine approximate agreement on graphs
LIPIcs
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
2019
2019-10-08T12:41:38Z
2020-01-16T12:38:14Z
conference
https://research-explorer.app.ist.ac.at/record/6931
https://research-explorer.app.ist.ac.at/record/6931.json
1908.02743
639378 bytes
application/pdf
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 xi and has to decide on an
output value yi 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 > (ω + 1)f,
where ω 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.