Search papers, labs, and topics across Lattice.
The paper investigates space-time trade-offs for population protocols on bounded-degree trees, focusing on leader election and exact majority problems. It demonstrates that, unlike complete graphs, bounded-degree trees do not exhibit significant space-time trade-offs for these problems, achieving near-optimal stabilization time with constant-space protocols. The authors introduce a fast self-stabilizing 2-hop coloring protocol and a self-stabilizing tree orientation algorithm, enabling linear speed-ups compared to existing methods.
Constant-space population protocols on bounded-degree trees can achieve near-optimal stabilization time for leader election and exact majority, defying the space-time trade-offs observed in complete graphs.
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. Our results are based on two novel protocols, which we believe are of independent interest. First, we give a new fast self-stabilising 2-hop colouring protocol for general interaction graphs, whose stabilisation time we bound using a stochastic drift argument. Second, we give a self-stabilising tree orientation algorithm that builds a rooted tree in optimal time on any tree. As a consequence, we can use simple constant-state protocols designed for directed trees to solve leader election and exact majority fast. For example, we show that ``directed''annihilation dynamics solve exact majority in $O(n^2 \log n)$ steps on directed trees.
