Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913177187385344 |
|---|---|
| author | Sudo, Yuichi |
| author_facet | Sudo, Yuichi |
| contents | We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size $n$. Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [BCC+21a] (PODC) showed that this problem can be solved in $O(n)$ expected time with $O(n)$ states. Recently, Gąsieniec, Grodzicki, and Stachowiak [GGS25] (PODC) proved that $n+O(\log n)$ states suffice to achieve $O(n \log n)$ time both in expectation and with high probability (w.h.p.). If substantially more states are available, sublinear time can be achieved. The authors of [BCC+21] presented a $2^{O(n^ρ\log n)}$-state SS-LE protocol with a parameter $ρ$: setting $ρ= Θ(\log n)$ yields an optimal $O(\log n)$ time both in expectation and w.h.p., while $ρ= Θ(1)$ results in $O(ρ\,n^{1/(ρ+1)})$ expected time. Recently, Austin, Berenbrink, Friedetzky, Götte, and Hintze [ABF+25] (PODC) presented a novel SS-LE protocol parameterized by a positive integer $ρ$ with $1 \le ρ< n/2$ that solves SS-LE in $O(\frac{n}ρ\cdot\log n)$ time w.h.p.\ using $2^{O(ρ^2\log n)}$ states. This paper independently presents yet another time--space tradeoff of SS-LE: for any positive integer $ρ$ with $2 \le ρ\le \sqrt{n}$, SS-LE can be achieved within $O\left(\frac{n}ρ\cdot \logρ\right)$ expected time using $2^{2ρ\lg^2ρ+ O(\log n)}$ states. The proposed protocol uses significantly fewer states than [ABF+25] for any expected stabilization time above $Θ(\sqrt{n}\log n)$. When $ρ= Θ\left(\frac{\log n}{\log^2 \log n}\right)$, the proposed protocol is the first to achieve sublinear time while using only polynomially many states. A limitation of our protocol is that the constraint $ρ\le\sqrt{n}$ prevents achieving $o(\sqrt{n}\log n)$ time, whereas the protocol of [ABF+25] can surpass this bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_23649 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time Sudo, Yuichi Distributed, Parallel, and Cluster Computing We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size $n$. Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [BCC+21a] (PODC) showed that this problem can be solved in $O(n)$ expected time with $O(n)$ states. Recently, Gąsieniec, Grodzicki, and Stachowiak [GGS25] (PODC) proved that $n+O(\log n)$ states suffice to achieve $O(n \log n)$ time both in expectation and with high probability (w.h.p.). If substantially more states are available, sublinear time can be achieved. The authors of [BCC+21] presented a $2^{O(n^ρ\log n)}$-state SS-LE protocol with a parameter $ρ$: setting $ρ= Θ(\log n)$ yields an optimal $O(\log n)$ time both in expectation and w.h.p., while $ρ= Θ(1)$ results in $O(ρ\,n^{1/(ρ+1)})$ expected time. Recently, Austin, Berenbrink, Friedetzky, Götte, and Hintze [ABF+25] (PODC) presented a novel SS-LE protocol parameterized by a positive integer $ρ$ with $1 \le ρ< n/2$ that solves SS-LE in $O(\frac{n}ρ\cdot\log n)$ time w.h.p.\ using $2^{O(ρ^2\log n)}$ states. This paper independently presents yet another time--space tradeoff of SS-LE: for any positive integer $ρ$ with $2 \le ρ\le \sqrt{n}$, SS-LE can be achieved within $O\left(\frac{n}ρ\cdot \logρ\right)$ expected time using $2^{2ρ\lg^2ρ+ O(\log n)}$ states. The proposed protocol uses significantly fewer states than [ABF+25] for any expected stabilization time above $Θ(\sqrt{n}\log n)$. When $ρ= Θ\left(\frac{\log n}{\log^2 \log n}\right)$, the proposed protocol is the first to achieve sublinear time while using only polynomially many states. A limitation of our protocol is that the constraint $ρ\le\sqrt{n}$ prevents achieving $o(\sqrt{n}\log n)$ time, whereas the protocol of [ABF+25] can surpass this bound. |
| title | Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2505.23649 |