Loosely-stabilizing Leader Election in Population Protocol Model

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 一般社団法人情報処理学会の論文
• 2009-05-04

著者

• Yukiko Yamauchi

  Graduate School of Information Science, Nara Institute of Science and Technology

• Yamauchi Yukiko

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Yukiko Yamauchi

  Graduate School Of Information Science Nara Institute Of Science And Technology Japan

• Yukiko Yamauchi

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Toshimitsu Masuzawa

  Graduate School Of Information Science And Technology Osaka University Osaka Japan.

• Junya Nakamura

  Graduate School Of Information Science And Technology Osaka University

• Yuichi Sudo

  Graduate School of Information Science and Technology, Osaka University

• Fukuhito Ooshita

  Graduate School of Information Science and Technology, Osaka University

• Hirotsugu Kakugawa

  Graduate School of Information Science and Technology, Osaka University

• Yuichi Sudo

  Graduate School Of Information Science And Technology Osaka University

• Fukuhito Ooshita

  Graduate School Of Information Science And Technology Osaka University Osaka Japan.

• Hirotsugu Kakugawa

  Graduate School Of Information Science And Technology Osaka University Japan

関連論文

• Probabilistic Methods for Spatio-Temporal Coverage in People-Centric Sensing
• Loosely-stabilizing Leader Election in Population Protocol Model
• Node Selection Methods for Probabilistic Coverage in People-Centric Sensing
• Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
• Rendezvous of Asynchronous Mobile Agents in Trees
• A self-stabilizing distributed algorithm for the multicoloring problem in dynamic networks
• Probabilistic Coverage Methods in People-Centric Sensing
• On Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on Three-interaction

スポンサーリンク