New theoretical basis of large scale dynamic distributed systems based on uncertain information and its applications

基于不确定信息的大规模动态分布式系统新理论基础及其应用

• 批准号: 19H04085
• 负责人: 増澤 利光
• 金额: $ 10.82万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19H04085/
• 关键词: 分散システム; 分散アルゴリズム; 動的ネットワーク; 不確かな情報; 大域タスク

大規模動的ネットワークで動作する分散システムでは，各ノードが情報を収集する間にネットワーク環境が変動しうる．このため，各ノードが収集した大域情報は不確かさを伴う．そこで本研究では，不確かな大域情報を前提とする分散アルゴリズムの新たな理論的基盤の確立を目指す．これまでに，以下の課題に取り組み，一定の成果を得た．1．ノードが収集した大域情報の不確かさを反映した新たなモデルの提案：動的ネットワーク環境において，各ノードが利用可能な情報を局所的な情報に限定したモデルを提案した．2．大域タスクが実現できるために必要な大域情報の正確さの度合の解明：大域タスクを実現するには，各ノードにおいてどのような大域情報がどの程度の正確さで利用できればよいかの解明を目指した．訪問ノードで情報を収集し，得られた不確かな大域情報を利用してタスク処理を行うモバイルエージェントに関する研究を進めた．また，２次元平面上のモバイルロボット群の集合問題について，ロボットの視野に欠損がある場合のアルゴリズムに関する研究を進めた．3．大域情報の範囲や正確さの度合いが，大域タスクの達成可能な正確性や効率に及ぼす影響の解明：大域情報の範囲や正確さの度合いが，実現できる大域タスクの正確性や効率に与える影響の解明を目指した．動的ネットワークの一種である個体群プロトコルモデルに関する様々な研究を進めた．各個体が持つ情報量と大域性をうまく制限することにより，最も基本的かつ重要な問題であるリーダ選挙問題を超高速に解くアルゴリズムを開発した．4．不確かな大域情報を前提とする分散アルゴリズムの設計フレームワークの確立：動的ネットワークにおいて大域タスクを実現するフレームワークの基盤として，大域的あるいは局所的にいくつかのプロセスを選出する自己安定分散アルゴリズムに関する研究を進めた．

The large-scale dynamic environment changes when the information is collected from the various sources. This is the first time that we've seen this. This study is aimed at establishing the basis of a new theory based on the premise of accurate global information. 1. To reflect the inaccuracy of global information collection, a new proposal is proposed to limit the use of local information in dynamic environments. 2. To clarify the accuracy of global information collection, a new proposal is proposed to limit the use of local information. The extent to which domain information is correctly utilized in each application is indicated in the following table. Access to information collection, access to accurate information, access to large areas of information, access to information processing, access to information, access to information collection, access to information collection, access information collection, access to information collection, access information collection, access to information collection, access to information collection, access 3. The range and accuracy of information in large domains and the degree of integration of information in large domains. The feasibility, efficiency and influence of information in large domains are explained. The scope and accuracy of global information are closely related, and the effectiveness and impact of global information on legitimacy are clearly indicated. A study on the relationship between individual population and dynamic life cycle has been carried out. The amount of information held by each individual is limited by the large domain. The most basic important problem is the selection problem. The ultra-high speed solution is developed. 4. The large domain information is not accurate. The premise is decentralized. The design of the system is established. The research on the stability and dispersion of the system has been carried out.

项目成果

Self-Stabilizing Population Protocols With Global Knowledge

• DOI: 10.1109/tpds.2021.3076769
• 发表时间: 2021-12
• 期刊: IEEE Transactions on Parallel and Distributed Systems
• 影响因子: 5.3
• 作者: Y. Sudo;M. Shibata;Junya Nakamura;Yonghwan Kim;T. Masuzawa

Communication efficient self-stabilizing leader election

通信高效自稳定领导者选举

• 发表时间: 2020
• 作者: Xavier Defago;Yuval Emek;Shay Kutten;Toshimitsu Masuzawa;Yasumasa Tamura
• 通讯作者: Yasumasa Tamura

University of Nevada, Las Vegas(米国)

内华达大学拉斯维加斯分校（美国）

Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights

带灯自主移动机器人的异步采集算法

• DOI: 10.1007/978-3-030-91081-5_27
• 发表时间: 2021
• 期刊: International Symposium on Stabilizing, Safety, and Security of Distributed Systems
• 作者: R. Nakai;Y. Sudo;K. Wada
• 通讯作者: K. Wada

Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols

群体协议中环上的时间最优自稳定领导者选举

• DOI: 10.1587/transfun.2020eap1125
• 发表时间: 2021
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: YOKOTA Daisuke;SUDO Yuichi;MASUZAWA Toshimitsu
• 通讯作者: MASUZAWA Toshimitsu