外乱に対して安定な分散アルゴリズムの相互作用パターン

抗干扰稳定的分布式算法的交互模式

• 批准号: 19K11826
• 负责人: 角川 裕次
• 金额: $ 2.83万
• 依托单位: Ryukoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11826/
• 关键词: 分散アルゴリズム; 自己安定; 分散グラフアルゴリズム; 自律分散システム; 故障耐性; 自己組織化; 自己安定アルゴリズム; 分散相互排除; プロセス同期; 相互排除; IoT; 自己安定システム; 独立集合; 個体群プロトコル; 分散システム

本研究は，自己安定の概念を基礎におき大規模な分散システムを対象として，ネットワーク変動に対する高度な自律性と適応性を実現する分散アルゴリズムの基礎理論に関するものである．特に分散システム内のノードは対等で，集中制御を行う特別なノードが無く，ノード総数が極めて膨大である分散システムを主な研究の対象とする．現在，無線ワイヤレスセンサネットワークではひとつのシステムにおいては数十程度の規模であるが，本研究の目的は，このような限定的なノード数を大きく越えて，大規模数のノードが対等に相互作用する自律的な分散システムの設計技法の確立を目指して研究を進めている．2022年度は主に，(1) マイナス支配集合問題の一般化，および，(2) 2-極小支配集合問題について，これらの問題に対する自己安定分散アルゴリズムの開発に取り組んで幾つかの成果を上げ，国際会議で発表を行った.マイナス支配集合問題の一般化に関する研究では，すでに知られているマイナス支配集合問題に対してマイナス(L,K,Z)支配集合問題という一般化の提案を行った．2-極小支配集合問題に関する研究では，準最適解である極小支配集合に対して準最適性を改善した2-極小支配集合を提案した．具体的には，支配集合に含まれる2つの頂点を除外し，新たに1つの頂点を追加する操作により，支配集合のサイズが減少できない場合を2-極小性と定めた．この2-極小性は準最適解ではあるものの，分散システムにおける局所的な情報交換で実現できることから，通信コストを抑えつつ解の改善を行うという点で応用上の観点から興味深い問題設定である．

这项研究基于自我稳定的概念，并关注分布式算法的基本理论，这些理论具有高水平的自主权和对网络波动的适应性，针对大型分布式系统。特别是，分布式系统中的节点相等，并且没有用于集中控制的特殊节点，并且节点的总数非常大，主要研究集中在分布式系统上。目前，一个系统的比例约为几十个，但是这项研究的目的是为自主分布式系统建立设计技术，其中大量节点以相等的基础相互作用，超过了这一有限数量的节点。在2022财政年度，我们主要致力于（1）负面对照组问题的概括和（2）2分钟的控制集问题，并取得了一些结果，并在国际会议上提出了一些结果。在我们对负面对照组问题的概括的研究中，我们提出了对已知的负面对照组问题的负面对照组问题的概括，称为负（L，K，Z）控制集问题。在对2分钟控制集问题的研究中，我们提出了一个2分钟的控制集，对2分钟控制集的次优度改进，这是一种次优的解决方案。具体而言，将2分钟的性定义为无法通过排除主要集合中包含的两个顶点并添加一个新顶点的两个顶点来减小主体集的大小的情况。尽管这种2分钟是一个次优的解决方案，但可以通过分布式系统中的本地信息交换来实现，因此从应用程序的角度来看是一个有趣的问题，因为它可以改善解决方案的同时降低通信成本。

项目成果

A linear-time self-stabilizing distributed algorithm for the minimal minus ($L, K, Z$) -domination problem under the distance-2 model

距离2模型下最小负($L,K,Z$)支配问题的线性时间自稳定分布式算法

• DOI: 10.1109/candarw57323.2022.00018
• 发表时间: 2022
• 期刊: The 14th International Workshop on Parallel and Distributed Algorithms and Applications (PDAA), in Proceedings of the 2022 Tenth International Symposium on Computing and Networking Workshops (CANDARW)
• 作者: Kakugawa Hirotsugu;Kamei Sayaka
• 通讯作者: Kamei Sayaka

Loosely-stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers nor Random Numbers

无标识符和随机数的群体协议中任意图的松散稳定领导者选举

• 发表时间: 2020
• 期刊: EICE Transactions on Information and Systems
• 作者: Yuichi Sudo;Fukuhito Ooshita;Hirotsugu Kakugawa;Toshimitsu Masuzawa
• 通讯作者: Toshimitsu Masuzawa

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

Time-Optimal Leader Election in Population Protocols

群体协议中的时间最优领导者选举

• DOI: 10.1109/tpds.2020.2991771
• 发表时间: 2020
• 期刊: IEEE Transactions on Parallel and Distributed Systems
• 影响因子: 5.3
• 作者: Sudo Yuichi;Ooshita Fukuhito;Izumi Taisuke;Kakugawa Hirotsugu;Masuzawa Toshimitsu
• 通讯作者: Masuzawa Toshimitsu

Protocol Model with Interaction 1 Probability Considering Speeds of Agents

考虑代理速度的交互 1 概率协议模型

• 发表时间: 2019
• 作者: Ryoya Sadano;Yuichi Sudo;Hirotsugu Kakugawa and Toshimitsu Masuzawa
• 通讯作者: Hirotsugu Kakugawa and Toshimitsu Masuzawa