文献

J-GLOBAL ID：202202217277675712   整理番号：22A0825999

個体群プロトコルモデルにおける任意グラフ上での自己安定リーダー選挙アルゴリズムの実装と評価

著者 (5件)： 渡辺啓太郎 (大阪大 基礎工) ,  小島英春 (大阪大 大学院情報科学研究科) ,  首藤裕一 (法政大 情報科学) ,  矢内直人 (大阪大 大学院情報科学研究科) ,  土屋達弘 (大阪大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 121  号： 356(NS2021 110-121)  ページ： 56-61 (WEB ONLY)  発行年： 2022年01月20日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 個体群プロトコルモデルとは,個体と呼ばれる移動する端末で構成されるセンサネットワークの1つである.個体は,通信可能範囲内に存在する個体とメッセージの交換を行い(交流),それぞれが保有する情報の交換を行う.個体群プロトコルモデル上でリーダー選出するリーダー選挙アルゴリズムは,多くの研究が行われており,さまざまな状況を対象にしたものが提案されている.個体間で交流を行い情報を交換することで,ある条件を満たした個体がリーダーとなる.リーダー選挙アルゴリズムにおいて個体は,なるべくやりとりする情報を少なく,交流回数を少なくすることが求められている.理論上,ある状況においては,やりとりする情報を最小にし,交流回数を最小にするアルゴリズムが提案されている.実環境においてこの様なアルゴリズムを利用するにあたっては,実装を行い評価を行う必要がある.そこで,本研究では,対象とするリーダー選挙アルゴリズムを実装し,エミュレーション環境上で動作させ実験を行い,評価を行う.リーダーがいない状況から,リーダーが1つに決定するまでの時間と一定期間においてリーダーが1つしか存在しない時間を計測する.実験では,リーダー選挙アルゴリズムで用いられるパラメータを変化させ,前述の評価項目がどのように変化するかを示す.(著者抄録)

シソーラス用語： *選択 ,  数学モデル ,  *個体群 ,  センサネットワーク ,  安定化 ,  有向グラフ ,  プロトコル ,  計算機アルゴリズム
準シソーラス用語： *リーダー選挙 ,  個体群モデル ,  自己安定化

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  計算機網  (JC03000K)

引用文献 (12件)：

• D. Angluin, J. Aspnes, Z. Diamadi, M.J. Fischer, and R. Peralta, “Computation in networks of passively mobile finite-state sensors,” Distributed computing, vol.18, no.4, pp.235-253, 2006.
• D. Angluin, J. Aspnes, and D. Eisenstat, “Fast computation by population protocols with a leader,” Distributed Comput., vol.21, no.3, pp.183-199, 2008.
• D. Angluin, J. Aspnes, M.J. Fischer, and H. Jiang, “Self-stabilizing population protocols,” ACM Transactions on Autonomous and Adaptive Systems, vol.3, no.4, pp.13:1-13:28, Dec. 2008.
• M.J. Fischer and H. Jiang, “Self-stabilizing leader election in networks of finite-state anonymous agents,” International Conference On Principles of Distributed Systems (OPODIS), ed. by A.A. Shvartsman, vol.4305, pp.395-409, Lecture Notes in Computer Science, Springer, 2006.
• S. Cai, T. Izumi, and K. Wada, “How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model,” Theory of Computing Systems, vol.50, no.3, pp.433-445, 2012.

タイトルに関連する用語 (9件)： 個体群 ,  プロトコル ,  モデル ,  グラフ ,  自己 ,  リーダー選挙 ,  アルゴリズム ,  実装 ,  評価