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

Masashi TSUCHIDA  Fukuhito OOSHITA  Michiko INOUE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.7   pp.1672-1682
Publication Date: 2020/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7311
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
mobile agent,  gathering problem,  Byzantine fault,  

Full Text: PDF(339.8KB)>>
Buy this Article




Summary: 
We propose two algorithms for the gathering of k mobile agents in asynchronous Byzantine environments. For both algorithms, we assume that graph topology is arbitrary, each node is equipped with an authenticated whiteboard, agents have unique IDs, and at most f weakly Byzantine agents exist. Here, a weakly Byzantine agent can make arbitrary behavior except falsifying its ID. Under these assumptions, the first algorithm achieves a gathering without termination detection in O(m+fn) moves per agent (m is the number of edges and n is the number of nodes). The second algorithm achieves a gathering with termination detection in O(m+fn) moves per agent by additionally assuming that agents on the same node are synchronized, $f<lceil rac{1}{3} k ceil$ holds, and agents know k. To the best of our knowledge, this is the first work to address the gathering problem of mobile agents for arbitrary topology networks in asynchronous Byzantine environments.