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

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

• 批准号: 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つのトークンが存在するような自己安定アルゴリズムの設計を行った．さらに，動的タスクや動的ネットワークを考えるために，低機能なモバイルロボットモデルを対象とした研究も進めており，本研究最終年度では，ビザンチン故障を起こしたモバイルロボットが存在する中での自己安定アルゴリズムの設計と，モバイルロボットをグリッドネットワーク上の最大独立点集合を形成する位置に配置する分散アルゴリズムの設計を行った．

The purpose of this study is to explore the problem of critical areas in various situations, and to form minimal dominant sets of computer sets in critical areas. In the final year, the dominant set problem is solved by solving the (L,K,Z) dominant set problem and the 2-minimal dominant set problem. In the future, the problem of moving forward will be solved through a new design and safety management plan. In addition, the existing status communication mode is fixed, and the mode is changed, and the mode is disappeared. In addition, the existing status communication mode is changed, and the mode is changed. In the final year of this study, we will continue to study the design of low-performance, low-performance, low-The design of a decentralized array of devices that are configured at locations that form the largest collection of independent points on the Internet has been implemented.

项目成果

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

Brief Announcement Forgive & Forget: Self-stabilizing Swarms in Spite of Byzantine Robots

简短公告 原谅

• DOI: 10.1007/978-3-030-34992-9_2
• 发表时间: 2019
• 期刊: Proc. 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems
• 作者: Ashkenazi Yotam;Dolev Shlomi;Kamei Sayaka;Ooshita Fukuhito;Wada Koichi
• 通讯作者: Wada Koichi