---
OA_place: publisher
OA_type: gold
_id: '22367'
abstract:
- lang: eng
  text: "We study the Undecided-State Dynamics (USD), a fundamental consensus process
    in which each vertex holds one of k decided opinions or the undecided state. We
    consider both the gossip model and the population protocol model. Prior work established
    tight bounds on the consensus time of this process only for the regime \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n⁡\r\nn\r\n)\r\n2\r\n)\r\n
    (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model),
    often under restrictive assumptions on the initial configuration.\r\nIn this paper,
    we obtain the first consensus-time guarantees for USD that hold for arbitrary
    2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and
    the population protocol model. In the gossip model, USD reaches consensus within
    \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\n synchronous rounds with
    probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing
    to the all-undecided state in the first round. In the population protocol model,
    USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n
    asynchronous interactions with high probability. We also present lower bounds
    that match the upper bounds up to polylogarithmic factors for a specific initial
    configuration and show that our upper bounds are essentially optimal."
acknowledgement: "Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837.
  Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST
  CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship
  from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous
  reviewers for their helpful comments and suggestions."
article_processing_charge: No
arxiv: 1
author:
- first_name: Colin
  full_name: Cooper, Colin
  last_name: Cooper
- first_name: Frederik
  full_name: Mallmann-Trenn, Frederik
  id: 68748c44-84d5-11f1-b4f6-ca083374e553
  last_name: Mallmann-Trenn
- first_name: Tomasz
  full_name: Radzik, Tomasz
  last_name: Radzik
- first_name: Nobutaka
  full_name: Shimizu, Nobutaka
  last_name: Shimizu
- first_name: Takeharu
  full_name: Shiraga, Takeharu
  last_name: Shiraga
citation:
  ama: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state
    dynamics with many opinions. In: <i>Proceedings of the Annual ACM Symposium on
    Principles of Distributed Computing</i>. Association for Computing Machinery;
    2026:77-87. doi:<a href="https://doi.org/10.1145/3796701.3815920">10.1145/3796701.3815920</a>'
  apa: 'Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., &#38; Shiraga, T.
    (2026). Undecided state dynamics with many opinions. In <i>Proceedings of the
    Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 77–87). Egham,
    United Kingdom: Association for Computing Machinery. <a href="https://doi.org/10.1145/3796701.3815920">https://doi.org/10.1145/3796701.3815920</a>'
  chicago: Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu,
    and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In <i>Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing</i>, 77–87.
    Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3796701.3815920">https://doi.org/10.1145/3796701.3815920</a>.
  ieee: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided
    state dynamics with many opinions,” in <i>Proceedings of the Annual ACM Symposium
    on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 77–87.
  ista: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided
    state dynamics with many opinions. Proceedings of the Annual ACM Symposium on
    Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
    Computing, 77–87.'
  mla: Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” <i>Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association
    for Computing Machinery, 2026, pp. 77–87, doi:<a href="https://doi.org/10.1145/3796701.3815920">10.1145/3796701.3815920</a>.
  short: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing, Association
    for Computing Machinery, 2026, pp. 77–87.
conference:
  end_date: 2026-07-10
  location: Egham, United Kingdom
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2026-07-06
corr_author: '1'
das_tickbox: '1'
date_created: 2026-07-19T22:01:47Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-21T07:54:01Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3796701.3815920
external_id:
  arxiv:
  - '2603.02636'
file:
- access_level: open_access
  checksum: 9ada61feba1e93fd72867a5ba4ee8bb8
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-21T07:51:58Z
  date_updated: 2026-07-21T07:51:58Z
  file_id: '22380'
  file_name: 2026_ACMPODC_Cooper.pdf
  file_size: 709077
  relation: main_file
  success: 1
file_date_updated: 2026-07-21T07:51:58Z
has_accepted_license: '1'
keyword:
- consensus dynamics
- undecided state dynamics
- gossip model
- population protocol model
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77-87
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
  Computing
publication_identifier:
  isbn:
  - '9798400725128'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Undecided state dynamics with many opinions
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
_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: 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: Symposium on Distributed Computing'
  start_date: 2019-10-14
date_created: 2019-10-08T12:41:38Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2025-07-10T11:54:03Z
day: '01'
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
month: '11'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2019'
...