Silent self-stabilizing ranking: time optimal and space efficient

Publikationstyp
Conference Paper
Date Issued
2025
Sprache
English
Author(s)
Berenbrink, Petra  
Elsässer, Robert  
Götte, Thorsten  
Hintze, Lukas  
Kaaser, Dominik 
Data Engineering E-19  
TORE-URI
https://hdl.handle.net/11420/58476
Start Page
934
End Page
944
Citation
45th IEEE International Conference on Distributed Computing Systems, ICDCS 2025
Contribution to Conference
45th IEEE International Conference on Distributed Computing Systems, ICDCS 2025  
Publisher DOI
10.1109/ICDCS63083.2025.00095
Scopus ID
2-s2.0-105019786045
Publisher
IEEE
ISBN of container
9798331517236
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,...,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(logn) states. Our protocol stabilizes in O(n2 logn) interactions w.h.p. and in expectation, using n + O(log2 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.
Subjects
Labeling
Leader Election
Population Protocols
Ranking
Self-Stabilization
DDC Class
600: Technology