Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913793164967936 |
|---|---|
| author | Berenbrink, Petra Elsässer, Robert Götte, Thorsten Hintze, Lukas Kaaser, Dominik |
| author_facet | Berenbrink, Petra Elsässer, Robert Götte, Thorsten Hintze, Lukas Kaaser, Dominik |
| contents | We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\log n)$ interactions w.h.p.\ and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC'21). In comparison to the currently best known ranking protocol by Burman et al., which requires $n + Ω(n)$ states, our result exponentially improves the number of overhead states. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10417 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient Berenbrink, Petra Elsässer, Robert Götte, Thorsten Hintze, Lukas Kaaser, Dominik Distributed, Parallel, and Cluster Computing We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\log n)$ interactions w.h.p.\ and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC'21). In comparison to the currently best known ranking protocol by Burman et al., which requires $n + Ω(n)$ states, our result exponentially improves the number of overhead states. |
| title | Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.10417 |