---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Colin
      foaf_name: Cooper, Colin
      foaf_surname: Cooper
  - foaf_Person:
      foaf_givenName: Frederik
      foaf_name: Mallmann-Trenn, Frederik
      foaf_surname: Mallmann-Trenn
      foaf_workInfoHomepage: http://www.librecat.org/personId=68748c44-84d5-11f1-b4f6-ca083374e553
  - foaf_Person:
      foaf_givenName: Tomasz
      foaf_name: Radzik, Tomasz
      foaf_surname: Radzik
  - foaf_Person:
      foaf_givenName: Nobutaka
      foaf_name: Shimizu, Nobutaka
      foaf_surname: Shimizu
  - foaf_Person:
      foaf_givenName: Takeharu
      foaf_name: Shiraga, Takeharu
      foaf_surname: Shiraga
  bibo_doi: 10.1145/3796701.3815920
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/9798400725128
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_subject:
  - consensus dynamics
  - undecided state dynamics
  - gossip model
  - population protocol model
  dct_title: Undecided state dynamics with many opinions@
...