Loosely-stabilizing Leader Election in Population Protocol Model

• Item type: SIG Technical Reports(1)
• 公開日: 2009-05-04
• タイトル: Loosely-stabilizing Leader Election in Population Protocol Model
• タイトル / 言語: en
• タイトル: Loosely-stabilizing Leader Election in Population Protocol Model
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Graduate School of Information Science, Nara Institute of Science and Technology
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: Yuichi, Sudo; Junya, Nakamura; Yukiko, Yamauchi; Fukuhito, Ooshita; Hirotsugu, Kakugawa; Toshimitsu, Masuzawa
• 著者名(英): Yuichi, Sudo; Junya, Nakamura; Yukiko, Yamauchi; Fukuhito, Ooshita; Hirotsugu, Kakugawa; Toshimitsu, Masuzawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A self-stabilizing protocol guarantees that, starting from an arbitrary initial configuration, a system eventually comes to satisfy its specification and keeps the specification forever. Although self-stabilizing protocols show excellent fault-tolerance against any transient faults (e.g. memory crash), designing self-stabilizing protocols is difficult and, what is worse, might be impossible due to the severe requirements. To circumvent the difficulty and impossibility, we introduce in this paper a novel notion of loose-stabilization. The loose-stabilization relaxes the closure requirement; starting from an arbitrary configuration, a system comes to satisfy its specification in a relatively short time, and it keeps the specification for a long time, though not forever. To show effectiveness and feasibility of the new concept, we present a probabilistic loosely-stabilizing leader election protocol in the Probabilistic Population Protocol (PPP) model of complete networks. The protocol elects a unique leader within O(nN log n) expected steps starting from any configuration, and keeps the unique leader for Ω(Ne N) expected steps, where n is the network size (not known to the protocol) and N is a known upper bound of n. This result proves that introduction of the loose-stabilization circumvents the already-known impossibility result; the self-stabilizing leader election in the PPP model of complete networks cannot be solved without knowledge on the exact network size.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A self-stabilizing protocol guarantees that, starting from an arbitrary initial configuration, a system eventually comes to satisfy its specification and keeps the specification forever. Although self-stabilizing protocols show excellent fault-tolerance against any transient faults (e.g. memory crash), designing self-stabilizing protocols is difficult and, what is worse, might be impossible due to the severe requirements. To circumvent the difficulty and impossibility, we introduce in this paper a novel notion of loose-stabilization. The loose-stabilization relaxes the closure requirement; starting from an arbitrary configuration, a system comes to satisfy its specification in a relatively short time, and it keeps the specification for a long time, though not forever. To show effectiveness and feasibility of the new concept, we present a probabilistic loosely-stabilizing leader election protocol in the Probabilistic Population Protocol (PPP) model of complete networks. The protocol elects a unique leader within O(nN log n) expected steps starting from any configuration, and keeps the unique leader for Ω(Ne N) expected steps, where n is the network size (not known to the protocol) and N is a known upper bound of n. This result proves that introduction of the loose-stabilization circumvents the already-known impossibility result; the self-stabilizing leader election in the PPP model of complete networks cannot be solved without knowledge on the exact network size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009-AL-124, 号 5, p. 1-8, 発行日 2009-05-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会