動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム

动态网络中动态任务的自适应容错分布式算法

• 批准号: 19K11828
• 负责人: 亀井 清華
• 金额: $ 2.66万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11828/
• 关键词: 動的分散問題; 自己安定アルゴリズム; 安全収束性; 低機能モバイルロボット; 危険区域問題; 支配集合問題; ロボットモデル; 2-極小支配集合問題; 相互排除問題; 分散アルゴリズム; 動的ネットワーク

本研究の目的としては，動的タスクのための自己安定アルゴリズムを安全に収束させることを掲げ，そのようなタスクの一つとして局所的危険区域問題を扱ってきたが，この問題では，各状況で危険区域内に入る計算機集合が極小支配集合を形成しているなどの特徴が見られることが分かってきた．そこで，最終年度は，マイナス支配集合問題やその拡張であるマイナス（L,K,Z)支配集合問題，さらに２－極小支配集合問題に対する自己安定アルゴリズムの設計を行い，それらの正しさを証明した．今後，これらの問題を動的タスクに拡張し，新たな自己安定アルゴリズムの設計および安全収束化を目指す計画である．また，既存の状態通信モデルを仮定したトークン巡回自己安定アルゴリズムにおいて，これをメッセージパッシングモデルに変換すると，トークンが消失する瞬間があることが分かっていたので，メッセージパッシングモデルに変換しても常に1つのトークンが存在するような自己安定アルゴリズムの設計を行った．さらに，動的タスクや動的ネットワークを考えるために，低機能なモバイルロボットモデルを対象とした研究も進めており，本研究最終年度では，ビザンチン故障を起こしたモバイルロボットが存在する中での自己安定アルゴリズムの設計と，モバイルロボットをグリッドネットワーク上の最大独立点集合を形成する位置に配置する分散アルゴリズムの設計を行った．

这项研究的目的是安全地收敛于动态任务的自我稳定算法，并将本地危险区问题视为这样的任务，但是已经发现，此问题具有在每种情况下形成最小占主导地位的危险区域内计算机集的特征。因此，在最后一年，我们为负面控制集问题，延伸，负（L，K，Z）控制设置问题和2分钟控制设置问题设计了一种自我稳定算法，并证明了它们的正确性。该计划是将这些问题扩展到动态任务，并设计新的自稳定算法并创建安全的融合。此外，在假定现有状态通信模型的令牌循环自我稳定算法中，众所周知，当将其转换为消息传递模型时，有一个时刻，令牌消失了，因此我们设计了一个自我稳定的算法，即使将一个令牌转换为消息传递模型，也总是有一个令牌。此外，我们还正在对低功能移动机器人模型进行研究，以考虑动态任务和动态网络。在这项研究的最后一年中，我们在遇到拜占庭故障的移动机器人的存在下设计了一种自我稳定算法，并且分布式算法位于移动机器人位于网格网络上最大的独立点集合的位置。

项目成果

A self-stabilizing token circulation with graceful handover on bidirectional ring networks

双向环网上优雅切换的自稳定代币流通

• 发表时间: 2022
• 期刊: International Journal of Networking and Computing
• 作者: Hirotsugu Kakugawa;Sayaka Kamei and Yoshiaki Katayama
• 通讯作者: Sayaka Kamei and Yoshiaki Katayama

A self-stabilizing 2-minimal dominating set algorithm based on loop composition in networks of girth at least 7

周长至少为 7 的网络中基于循环组合的自稳定 2 最小支配集算法

• DOI: 10.1109/ipdps53621.2022.00114
• 发表时间: 2022
• 期刊: n Proceedings of the 36th IEEE International Parallel & Distributed Processing Symposium (IPDPS)
• 作者: Maruyama Syohei;Sudo Yuichi;Kamei Sayaka;Kakugawa Hirotsugu
• 通讯作者: Kakugawa Hirotsugu

ソルボンヌ大学(フランス)

索邦大学（法国）

Autonomous Distributed Systems of Myopic Mobile Robots with Lights

带灯近视移动机器人自主分布式系统

• 发表时间: 2021
• 作者: Sayaka Kamei;Anissa Lamani;Fukuhito Ooshita;Sebastien Tixeuil and Koichi Wada;Sayaka Kamei
• 通讯作者: Sayaka Kamei

Gathering on rings for myopic asynchronous robots with lights

带灯近视异步机器人聚集环

• 发表时间: 2019
• 作者: Sayaka Kamei;Anissa Lamani;Fukuhito Ooshita;Sebastien Tixeuil;and Koichi Wada
• 通讯作者: and Koichi Wada