4 papers
Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics
Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu +2
How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous -Majority, in which every node in…
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…
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…
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,…