Introduces CIRCLES protocol that computes relative majority with k^3 states via circular lists where no two agents of same color share a list.
Fast consensus via the unconstrained undecided state dynam- ics
4 Pith papers cite this work, alongside 11 external citations. Polarity classification is still indexing.
4
Pith papers citing it
11
external citations · Crossref
fields
cs.DC 4representative citing papers
For the h-majority dynamics on n nodes with k opinions, if the initial plurality opinion has support x = ω(log n) and bias B0 = ω(√x), then for h = ω(n log n / x) the process reaches plurality consensus in O(log n) rounds with high probability.
The paper shows that for plurality consensus in the population protocol model, undecided state dynamics requires Ω(k log(√n/(k log n))) parallel time, almost matching the known O(k log n) upper bound.
citing papers explorer
-
Ranking Opinions with Few States in Population Protocols
Introduces CIRCLES protocol that computes relative majority with k^3 states via circular lists where no two agents of same color share a list.
-
On the $h$-majority dynamics with many opinions
For the h-majority dynamics on n nodes with k opinions, if the initial plurality opinion has support x = ω(log n) and bias B0 = ω(√x), then for h = ω(n log n / x) the process reaches plurality consensus in O(log n) rounds with high probability.
-
An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model
The paper shows that for plurality consensus in the population protocol model, undecided state dynamics requires Ω(k log(√n/(k log n))) parallel time, almost matching the known O(k log n) upper bound.
- Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density