Time-Space Trade-offs in Population Protocols

DOI10.1137/1.9781611974782.169zbMath1410.68118arXiv1602.08032OpenAlexW2952048613MaRDI QIDQ4575918

James Aspnes, Dan Alistarh, David Eisenstat, Rati Gelashvili, Ronald L. Rivest

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.08032

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Related Items

Simple and fast approximate counting and leader election in populations ⋮ Data Collection in Population Protocols with Non-uniformly Random Scheduler ⋮ Unnamed Item ⋮ On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Leader Election Requires Logarithmic Time in Population Protocols ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ Lower bounds on the state complexity of population protocols ⋮ Fast and succinct population protocols for Presburger arithmetic ⋮ Parameterized Analysis of Immediate Observation Petri Nets ⋮ Approximate majority analyses using tri-molecular chemical reaction networks ⋮ Unnamed Item ⋮ A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States ⋮ Population protocols: beyond runtime analysis ⋮ Unnamed Item ⋮ Computational Complexity of Atomic Chemical Reaction Networks ⋮ Expressive Power of Broadcast Consensus Protocols ⋮ Running time analysis of broadcast consensus protocols ⋮ Uniform bipartition in the population protocol model with arbitrary graphs ⋮ Automatic Analysis of Expected Termination Time for Population Protocols ⋮ A survey of size counting in population protocols ⋮ Stable leader election in population protocols requires linear time ⋮ Time-space trade-offs in population protocols for the majority problem ⋮ The complexity of verifying population protocols ⋮ Unnamed Item ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States ⋮ Composable computation in discrete chemical reaction networks ⋮ Robustness of Expressivity in Chemical Reaction Networks ⋮ New bounds for the flock-of-birds problem