3 papers
cs.DC2026
Undecided State Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of decided opinions or the undecided state. We consider both the gos…
cs.DC2025
3-Majority and 2-Choices with Many Opinions
Nobutaka Shimizu, Takeharu Shiraga
We present the first nearly-optimal bounds on the consensus time for the well-known synchronous consensus dynamics, specifically 3-Majority and 2-Choices, for an arbitrary number o…
cs.DC2024
Asynchronous 3-Majority Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with vertices, each vertex starting with one of initial opinions. At each discrete time step,…