conference paper published yes Colin Cooper author Frederik Mallmann-Trenn author 68748c44-84d5-11f1-b4f6-ca083374e553 Tomasz Radzik author Nobutaka Shimizu author Takeharu Shiraga author MoHe department PODC: Symposium on Principles of Distributed Computing 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 k = O ( n / ( log ⁡ n ) 2 ) (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. In 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 O ~ ( min { k , 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 O ~ ( min { k n , n 3 / 2 } ) 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. https://research-explorer.ista.ac.at/download/22367/22380/2026_ACMPODC_Cooper.pdf application/pdfno Association for Computing Machinery2026Egham, United Kingdom eng consensus dynamicsundecided state dynamicsgossip modelpopulation protocol model 9798400725128 2603.0263610.1145/3796701.3815920 77-87 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>. 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> 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. 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. 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> 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. 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>. 223672026-07-19T22:01:47Z2026-07-21T07:54:01Z