Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards

Masashi TSUCHIDA  Fukuhito OOSHITA  Michiko INOUE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.3   pp.602-610
Publication Date: 2018/03/01
Online ISSN: 1745-1361
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)
>>Buy this Article


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 Õ(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.