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

Yuichi SUDO; Fukuhito OOSHITA; Hirotsugu KAKUGAWA; Toshimitsu MASUZAWA

doi:10.1587/transinf.2019FCP0003

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

Yuichi SUDO, Fukuhito OOSHITA, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA

Full Text Views

0

Cite this

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(mn²d log n+mNΔ² log N) expected steps and keeps the unique leader for Ω(Ne^N) expected steps, where m is the number of edges and d is the diameter of the graph.

Publication: IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.489-499

Publication Date: 2020/03/01

Publicized: 2019/11/27

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

Authors

Yuichi SUDO
  Osaka University
Fukuhito OOSHITA
  Nara Institute of Science and Technology
Hirotsugu KAKUGAWA
  Ryukoku University
Toshimitsu MASUZAWA
  Osaka University

Keyword

population protocols, leader election, loose stabilization

Cite this

Copy

Yuichi SUDO, Fukuhito OOSHITA, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA, "Loosely Stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers or Random Numbers" in IEICE TRANSACTIONS on Information, vol. E103-D, no. 3, pp. 489-499, March 2020, doi: 10.1587/transinf.2019FCP0003.
Abstract: 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(mn²d log n+mNΔ² log N) expected steps and keeps the unique leader for Ω(Ne^N) expected steps, where m is the number of edges and d is the diameter of the graph.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0003/_p

Copy

@ARTICLE{e103-d_3_489,
author={Yuichi SUDO, Fukuhito OOSHITA, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Loosely Stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers or Random Numbers},
year={2020},
volume={E103-D},
number={3},
pages={489-499},
abstract={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(mn²d log n+mNΔ² log N) expected steps and keeps the unique leader for Ω(Ne^N) expected steps, where m is the number of edges and d is the diameter of the graph.},
keywords={},
doi={10.1587/transinf.2019FCP0003},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Loosely Stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers or Random Numbers
T2 - IEICE TRANSACTIONS on Information
SP - 489
EP - 499
AU - Yuichi SUDO
AU - Fukuhito OOSHITA
AU - Hirotsugu KAKUGAWA
AU - Toshimitsu MASUZAWA
PY - 2020
DO - 10.1587/transinf.2019FCP0003
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - 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(mn²d log n+mNΔ² log N) expected steps and keeps the unique leader for Ω(Ne^N) expected steps, where m is the number of edges and d is the diameter of the graph.
ER -