---
res:
  bibo_abstract:
  - "We revisit the majority problem in the population protocol communication model,
    as first studied by Angluin et al. (Distributed Computing 2008). We consider a
    more general version of this problem known as plurality consensus, which has already
    been studied intensively in the literature. In this problem, each node in a system
    of n nodes, has initially one of k different opinions, and they need to agree
    on the (relative) majority opinion. In particular, we consider the important and
    intensively studied model of Undecided State Dynamics.\r\nOur main contribution
    is an almost tight lower bound on the stabilization time: we prove that there
    exists an initial configuration, even with bias \\Delta = \\omega(\\sqrt{n\\log
    n}), where stabilization requires \\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})
    interactions, or equivalently, \\Omega(k\\log \\frac {\\sqrt n} {k \\log n}) parallel
    time for any k = o\\left(\\frac {\\sqrt n}{\\log n}\\right). This bound is tight
    for any k \\le n^{\\frac 1 2 - \\epsilon}, where \\epsilon >0 can be any small
    constant, as Amir et al.~(PODC'23) gave a O(k\\log n) parallel time upper bound
    for k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right).@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Antoine
      foaf_name: El-Hayek, Antoine
      foaf_surname: El-Hayek
      foaf_workInfoHomepage: http://www.librecat.org/personId=888a098e-fcac-11ee-aff7-d347be57b725
    orcid: 0000-0003-4268-7368
  - foaf_Person:
      foaf_givenName: Robert
      foaf_name: Elsässer, Robert
      foaf_surname: Elsässer
  - foaf_Person:
      foaf_givenName: Stefan
      foaf_name: Schmid, Stefan
      foaf_surname: Schmid
  bibo_doi: 10.1145/3732772.3733505
  dct_date: 2025^xs_gYear
  dct_identifier:
  - UT:001525534800066
  dct_isPartOf:
  - http://id.crossref.org/issn/ 9798400718854
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: An almost tight lower bound for plurality consensus with undecided state
    dynamics in the population protocol model@
...