Byzantine approximate agreement on graphs

T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 29:1--29:17.

Download
OA 639.38 KB

Conference Paper | Published | English
Author
;
Department
Series Title
LIPIcs
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 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.
Publishing Year
Date Published
2019-01-01
Proceedings Title
33rd International Symposium on Distributed Computing
Volume
146
Page
29:1--29:17
Conference
DISC: International Symposium on Distributed Computing
Conference Location
Budapest, Hungary
Conference Date
2019-10-14 – 2019-10-18
IST-REx-ID

Cite this

Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: 33rd International Symposium on Distributed Computing. Vol 146. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2019:29:1--29:17. doi:10.4230/LIPICS.DISC.2019.29
Nowak, T., & Rybicki, J. (2019). Byzantine approximate agreement on graphs. In 33rd International Symposium on Distributed Computing (Vol. 146, p. 29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPICS.DISC.2019.29
Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” In 33rd International Symposium on Distributed Computing, 146:29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.29.
T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in 33rd International Symposium on Distributed Computing, Budapest, Hungary, 2019, vol. 146, p. 29:1--29:17.
Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd International Symposium on Distributed Computing. DISC: International Symposium on Distributed Computing, LIPIcs, vol. 146. 29:1--29:17.
Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” 33rd International Symposium on Distributed Computing, vol. 146, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 29:1--29:17, doi:10.4230/LIPICS.DISC.2019.29.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-10-08T12:47:19Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1908.02743

Search this title in

Google Scholar