---
_id: '6931'
abstract:
- lang: eng
  text: "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."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas
  full_name: Nowak, Thomas
  last_name: Nowak
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
citation:
  ama: 'Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: <i>33rd
    International Symposium on Distributed Computing</i>. Vol 146. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:<a href="https://doi.org/10.4230/LIPICS.DISC.2019.29">10.4230/LIPICS.DISC.2019.29</a>'
  apa: 'Nowak, T., &#38; Rybicki, J. (2019). Byzantine approximate agreement on graphs.
    In <i>33rd International Symposium on Distributed Computing</i> (Vol. 146, p.
    29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPICS.DISC.2019.29">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>'
  chicago: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
    In <i>33rd International Symposium on Distributed Computing</i>, 146:29:1--29:17.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.DISC.2019.29">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>.
  ieee: T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in <i>33rd
    International Symposium on Distributed Computing</i>, Budapest, Hungary, 2019,
    vol. 146, p. 29:1--29:17.
  ista: '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.'
  mla: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
    <i>33rd International Symposium on Distributed Computing</i>, vol. 146, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:<a href="https://doi.org/10.4230/LIPICS.DISC.2019.29">10.4230/LIPICS.DISC.2019.29</a>.
  short: T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.
conference:
  end_date: 2019-10-18
  location: Budapest, Hungary
  name: 'DISC: International Symposium on Distributed Computing'
  start_date: 2019-10-14
date_created: 2019-10-08T12:41:38Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:09:38Z
ddc:
- '004'
department:
- _id: DaAl
doi: 10.4230/LIPICS.DISC.2019.29
ec_funded: 1
external_id:
  arxiv:
  - '1908.02743'
file:
- access_level: open_access
  checksum: 2d2202f90c6ac991e50876451627c4b5
  content_type: application/pdf
  creator: jrybicki
  date_created: 2019-10-08T12:47:19Z
  date_updated: 2020-07-14T12:47:44Z
  file_id: '6934'
  file_name: LIPIcs-DISC-2019-29.pdf
  file_size: 639378
  relation: main_file
file_date_updated: 2020-07-14T12:47:44Z
has_accepted_license: '1'
intvolume: '       146'
keyword:
- consensus
- approximate agreement
- Byzantine faults
- chordal graphs
- lattice agreement
language:
- iso: eng
oa: 1
oa_version: Published Version
page: 29:1--29:17
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 33rd International Symposium on Distributed Computing
publication_identifier:
  eisbn:
  - 978-3-95977-126-9
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Byzantine approximate agreement on graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2019'
...