---
res:
bibo_abstract:
- "Consider a distributed system with n processors out of which f can be Byzantine
faulty. In the\r\napproximate agreement task, each processor i receives an input
value xi and has to decide on an\r\noutput value yi such that\r\n1. the output
values are in the convex hull of the non-faulty processors’ input values,\r\n2.
the output values are within distance d of each other.\r\n\r\n\r\nClassically,
the values are assumed to be from an m-dimensional Euclidean space, where m ≥
1.\r\nIn this work, we study the task in a discrete setting, where input values
with some structure\r\nexpressible as a graph. Namely, the input values are vertices
of a finite graph G and the goal is to\r\noutput vertices that are within distance
d of each other in G, but still remain in the graph-induced\r\nconvex hull of
the input values. For d = 0, the task reduces to consensus and cannot be solved
with\r\na deterministic algorithm in an asynchronous system even with a single
crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous
systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of
G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant
of lattice agreement. For synchronous systems, we show tight resilience bounds
for the exact\r\nvariants of these and related tasks over a large class of combinatorial
structures.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Thomas
foaf_name: Nowak, Thomas
foaf_surname: Nowak
- foaf_Person:
foaf_givenName: Joel
foaf_name: Rybicki, Joel
foaf_surname: Rybicki
foaf_workInfoHomepage: http://www.librecat.org/personId=334EFD2E-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-6432-6646
bibo_doi: 10.4230/LIPICS.DISC.2019.29
bibo_volume: 146
dct_date: 2019^xs_gYear
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik@
dct_subject:
- consensus
- approximate agreement
- Byzantine faults
- chordal graphs
- lattice agreement
dct_title: Byzantine approximate agreement on graphs@
...