Introduces CIRCLES protocol that computes relative majority with k^3 states via circular lists where no two agents of same color share a list.
The computational power of population protocols.Distributed Computing, 20(4):279–304
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
Demand-aware topologies achieve at least 5/8 asymptotic throughput in the worst case, separating from the demand-oblivious bound of n/(2n-1) ≈ 1/2; computing optimal weak throughput is NP-hard while direct throughput is polynomial-time solvable.
Direct competition enables high-probability majority consensus in microbial populations for initial gaps Omega(sqrt(n log n)), while its absence requires Omega(n) gaps for constant probability.
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.
-
A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput
Demand-aware topologies achieve at least 5/8 asymptotic throughput in the worst case, separating from the demand-oblivious bound of n/(2n-1) ≈ 1/2; computing optimal weak throughput is NP-hard while direct throughput is polynomial-time solvable.
-
Reaching Agreement in Competitive Microbial Systems
Direct competition enables high-probability majority consensus in microbial populations for initial gaps Omega(sqrt(n log n)), while its absence requires Omega(n) gaps for constant probability.