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
조회수
132
우리는 인구 프로토콜 모델의 방향성 링에 대한 자체 안정화 리더 선택 프로토콜을 제안합니다. 상한이 주어지면 N 인구 규모에 대해 n, 제안된 프로토콜은 내에서 고유한 리더를 선출합니다. O(nN) 모든 구성 및 사용에서 시작되는 예상 단계 O(N) 상태. 이 수렴 시간은 주어진 상한이 다음과 같은 경우 최적입니다. N 점근적으로 빡빡합니다. 즉, N=O(n).
Daisuke YOKOTA
Osaka University
Yuichi SUDO
Hosei 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.
부
Daisuke YOKOTA, Yuichi SUDO, Toshimitsu MASUZAWA, "Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 12, pp. 1675-1684, December 2021, doi: 10.1587/transfun.2020EAP1125.
Abstract: We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N=O(n).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020EAP1125/_p
부
@ARTICLE{e104-a_12_1675,
author={Daisuke YOKOTA, Yuichi SUDO, Toshimitsu MASUZAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols},
year={2021},
volume={E104-A},
number={12},
pages={1675-1684},
abstract={We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N=O(n).},
keywords={},
doi={10.1587/transfun.2020EAP1125},
ISSN={1745-1337},
month={December},}
부
TY - JOUR
TI - Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1675
EP - 1684
AU - Daisuke YOKOTA
AU - Yuichi SUDO
AU - Toshimitsu MASUZAWA
PY - 2021
DO - 10.1587/transfun.2020EAP1125
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2021
AB - We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N=O(n).
ER -