-
- HIROSE Jion
- Nara Institute of Science and Technology
-
- NAKAMURA Junya
- Toyohashi University of Technology
-
- OOSHITA Fukuhito
- Nara Institute of Science and Technology
-
- INOUE Michiko
- Nara Institute of Science and Technology
抄録
<p>We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n4·|Λgood|·X(n)) rounds, where |Λgood| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f2+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|Λgood|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|Λall|)·X(N)) rounds, where |Λall| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |Λall|=O(|Λgood|) holds.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E105.D (3), 541-555, 2022-03-01
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390854717417496064
-
- NII論文ID
- 130008165592
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10061/0002000210
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可