IEICE TRANSACTIONS on Information
Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated Whiteboards
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.7 pp.1672-1682
- Publication Date
- 2020/07/01
- Publicized
- 2020/04/15
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019EDP7311
- Type of Manuscript
- PAPER
- Category
- Dependable Computing
Authors
Masashi TSUCHIDA
Nara Institute of Science and Technology
Fukuhito OOSHITA
Nara Institute of Science and Technology
Michiko INOUE
Nara Institute of Science and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masashi TSUCHIDA, Fukuhito OOSHITA, Michiko INOUE, "Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated Whiteboards" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 7, pp. 1672-1682, July 2020, doi: 10.1587/transinf.2019EDP7311.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7311/_p
Copy
@ARTICLE{e103-d_7_1672,
author={Masashi TSUCHIDA, Fukuhito OOSHITA, Michiko INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated Whiteboards},
year={2020},
volume={E103-D},
number={7},
pages={1672-1682},
abstract={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.},
keywords={},
doi={10.1587/transinf.2019EDP7311},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated Whiteboards
T2 - IEICE TRANSACTIONS on Information
SP - 1672
EP - 1682
AU - Masashi TSUCHIDA
AU - Fukuhito OOSHITA
AU - Michiko INOUE
PY - 2020
DO - 10.1587/transinf.2019EDP7311
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2020
AB - 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.
ER -
English
