On Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on Three-interaction

スポンサーリンク

概要

• 論文の詳細を見る

• A population protocol is a distributed computing model for passively mobile systems, in which a computation is executed by interactions between two agents. This paper is concerned with an extended model, population protocol by interactions of three agents. Leader election is a fundamental problem in distributed systems, to select a central coordinator. Cai, Izumi, Wada(2011) showed that the space complexity of a self-stabilizing leader election for n agents is exactly n. This paper shows that the space complexity of the self-stabilizing leader election in a population protocol by interactions of three agents (SS-LE PP3 for short) is exactly 「n+1/2」.

• 2013-02-22

著者

• 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

  Kyushu University Japan

• Shuji Kijima

  Graduate School Of Information Science And Electrical Engineering Kyushu University

• Masafumi Yamashita

  Kyushu University

• Xiaoguang Xu

  Kyushu University

• Shuji Kijima

  Kyushu University

• Yukiko Yamauchi

  Kyushu University

関連論文

• Loosely-stabilizing Leader Election in Population Protocol Model
• Online Prediction over Permutahedron
• Node Selection Methods for Probabilistic Coverage in People-Centric Sensing
• Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
• A self-stabilizing distributed algorithm for the multicoloring problem in dynamic networks
• Approximating the path-distance-width for k-cocomparability graphs
• On Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on Three-interaction

スポンサーリンク