Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards
-
- TSUCHIDA Masashi
- Nara Institute of Science and Technology
-
- OOSHITA Fukuhito
- Nara Institute of Science and Technology
-
- INOUE Michiko
- Nara Institute of Science and Technology
この論文をさがす
抄録
<p>We propose an algorithm for the gathering problem of mobile agents in arbitrary networks (graphs) with Byzantine agents. Our algorithm can make all correct agents meet at a single node in O(fm) time (f is the upper bound of the number of Byzantine agents and m is the number of edges) under the assumption that agents have unique ID and behave synchronously, each node is equipped with an authenticated whiteboard, and f is known to agents. Here, the whiteboard is a node memory where agents can leave information. Since the existing algorithm achieves gathering without a whiteboard in Õ(n9λ) time, where n is the number of nodes and λ is the length of the longest ID, our algorithm shows an authenticated whiteboard can significantly reduce the time for the gathering problem in Byzantine environments.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E101.D (3), 602-610, 2018
一般社団法人 電子情報通信学会
- Tweet
詳細情報
-
- CRID
- 1390001204381269376
-
- NII論文ID
- 130006414052
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10061/12556
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可