• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 18 Feb 2026] Title:Near-optimal population protocols on bounded-degree trees View PDF HTML (experimental)Abstract:We investigate space-time trade-offs for population protocols in sparse interaction graphs. • In complete interaction graphs, optimal space-time trade-offs are known for the leader election and exact majority problems. • However, it has remained open if other graph families exhibit similar space-time complexity trade-offs, as existing lower bound techniques do not extend beyond highly dense graphs. • In this work, we show that – unlike in complete graphs – population protocols on bounded-degree trees do not exhibit significant asymptotic space-time trade-offs for leader election and exact majority. • For these problems, we give constant-space protocols that have near-optimal worst-case expected stabilisation time. • These new protocols achieve a linear speed-up compared to the state-of-the-art.
Article Summaries:
- Researchers have shown that population protocols on bounded‑degree trees can achieve near‑optimal performance without the space‑time trade‑offs seen in complete graphs. The study presents constant‑space algorithms that stabilize in expected time close to the theoretical minimum, providing a linear speed‑up over existing methods for leader election and exact majority. Two new protocols underpin this advance: a fast self‑stabilizing 2‑hop coloring scheme for general graphs and a self‑stabilizing tree‑orientation algorithm that constructs a rooted tree in optimal time. These tools enable simple directed‑tree protocols-such as annihilation dynamics-to solve exact majority in (O(n^2\log n)) steps, marking a significant step forward in distributed computing on sparse networks.
Sources: