The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
우리는 Angluin et al.이 제안한 인구 프로토콜 모델의 리더 선택 문제를 고려합니다. 프로토콜이 노드의 정확한 수를 알지 못하면 완전한 그래프, 임의 그래프, 트리, 선, 차수 제한 그래프 등에 대해 자체 안정화 리더 선택이 불가능합니다. 2004년에는 불가능함을 극복하기 위해 우리는 다음과 같은 개념을 도입했습니다. 느슨한 안정화, 이는 자체 안정화에 대한 폐쇄 요구 사항을 완화합니다. 느슨하게 안정화된 프로토콜은 초기 구성부터 시작하여 시스템이 안전한 구성에 도달하고 그 후에 시스템이 해당 사양(e.g., 독특한 리더) 영원히는 아니지만 충분히 오랫동안 (e.g., 노드 수에 비해 기하급수적으로 긴 시간입니다). 이전 연구에서는 임의 그래프에 대해 느슨하게 안정화된 두 가지 리더 선택 프로토콜을 제시했습니다. 하나는 에이전트 식별자를 사용하고 다른 하나는 난수를 사용하여 고유한 리더를 선출합니다. 본 논문에서는 에이전트 식별자나 난수 없이 임의의 그래프에서 리더 선택을 해결하는 느슨하게 안정화된 프로토콜을 제시합니다. 주어진 상한 N 및 노드 수의 Δ n 및 노드의 최대 수준 δ는 각각 제안된 프로토콜이 안전한 구성에 도달합니다. O(mn2d 기록 n+mNΔ2 기록 N) 예상 단계를 수행하고 Ω(NeN) 예상 단계, 여기서 m 는 모서리의 수이고 d 그래프의 직경입니다.
Yuichi SUDO
Osaka University
Fukuhito OOSHITA
Nara Institute of Science and Technology
Hirotsugu KAKUGAWA
Ryukoku University
Toshimitsu MASUZAWA
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
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(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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0003/_p
부
@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(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.},
keywords={},
doi={10.1587/transinf.2019FCP0003},
ISSN={1745-1361},
month={March},}
부
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(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.
ER -