2026-07-22T12:15:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11336 2024-03-06T10:47:59Z ddc:004 open_access

Byzantine Approximate Agreement on Graphs Nowak, Thomas Rybicki, Joel consensus approximate agreement Byzantine faults chordal graphs lattice agreement 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Nowak and Joel Rybicki 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.29 urn:nbn:de:0030-drops-113363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode