
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

ByzantineTolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards
Masashi TSUCHIDA Fukuhito OOSHITA Michiko INOUE
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E101D
No.3
pp.602610 Publication Date: 2018/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2017FCP0008
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —) Category: Keyword: mobile agent, gathering problem, Byzantine fault,
Full Text: PDF(378.4KB)>>
Summary:
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 Õ(n^{9}λ) 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.

