Loosely Stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers or Random Numbers

Yuichi SUDO  Fukuhito OOSHITA  Hirotsugu KAKUGAWA  Toshimitsu MASUZAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.489-499
Publication Date: 2020/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019FCP0003
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Category: 
Keyword: 
population protocols,  leader election,  loose stabilization,  

Full Text: PDF(443.1KB)>>
Buy this Article




Summary: 
We consider the leader election problem in the population protocol model, which Angluin et al. proposed in 2004. A self-stabilizing leader election is impossible for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs, and so on unless the protocol knows the exact number of nodes. In 2009, to circumvent the impossibility, we introduced the concept of loose stabilization, which relaxes the closure requirement of self-stabilization. A loosely stabilizing protocol guarantees that starting from any initial configuration, a system reaches a safe configuration, and after that, the system keeps its specification (e.g., the unique leader) not forever but for a sufficiently long time (e.g., an exponentially long time with respect to the number of nodes). Our previous works presented two loosely stabilizing leader election protocols for arbitrary graphs; one uses agent identifiers, and the other uses random numbers to elect a unique leader. In this paper, we present a loosely stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers or random numbers. Given upper bounds N and Δ of the number of nodes n and the maximum degree of nodes δ, respectively, the proposed protocol reaches a safe configuration within O(mn2d log n+mNΔ2 log N) expected steps and keeps the unique leader for Ω(NeN) expected steps, where m is the number of edges and d is the diameter of the graph.