Journal
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume 30, Issue 6, Pages 1359-1373Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2018.2881125
Keywords
Population protocols; loose-stabilization; leader election; the same speed timer
Funding
- JSPS KAKENHI [17K19977, 16K00018, 18K11167, 18K18000]
- Japan Science and Technology Agency (JST) SICORP
- Grants-in-Aid for Scientific Research [16K00018, 18K11167, 17K19977, 18K18000] Funding Source: KAKEN
Ask authors/readers for more resources
In the population protocol model [Angluin et al. 2006], it is impossible to design a self-stabilizing leader election protocol without any knowledge of the exact number of nodes in the system. The notion of loose-stabilization, which relaxes the closure requirement of self-stabilization, was introduced in 2009 to circumvent this impossibility. The notion can be described as follows: a loosely-stabilizing protocol guarantees that, starting from any initial configuration, a system reaches a safe configuration eventually, and after that, the system maintains its specification (e.g., the unique leader) not forever, but for a sufficiently long time. The previous work of the authors presented a loosely-stabilizing protocol that solves the leader election on complete graphs using only a given upper bound N on the number of nodes n in the system, instead of the exact value of n. In this paper, we propose two loosely-stabilizing protocols that solve leader election for arbitrary graphs. One is a deterministic protocol that uses the unique identifiers of nodes while the other is a probabilistic protocol that works on anonymous networks. Given an upper bound N on the number of nodes, both protocols maintain a unique leader for Omega(Ne-2N) thorn expected steps (holding time) after entering a safe configuration. The first algorithm enters a safe configuration within O(mN log n) expected steps (convergence time) while the second one does this within O(mN(2) log n) expected steps, where m is the number of edges in the graph. Both protocols require only O(log N) bits for each node's memory. A novel concept, called the same speed timer is introduced, by which all nodes of the system can count down their timers at the same speed. This concept allows to achieve fast convergence time of both algorithms. To design the second protocol, we design a self-stabilizing two-hop coloring protocol, which is interesting in its own right. This protocol uses only O(log N) memory space per node. We establish a lower bound. Any loosely-stabilizing leader election protocol with expected exponential holding time requires Omega(mN) expected convergence time. This lower bound shows a near-optimality of the first algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available