IEICE TRANSACTIONS on Information
Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E101-D No.3 pp.602-610
- Publication Date
- 2018/03/01
- Publicized
- 2017/12/19
- 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
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 Arbitrary Networks with Authenticated Whiteboards" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 3, pp. 602-610, March 2018, doi: 10.1587/transinf.2017FCP0008.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017FCP0008/_p
Copy
@ARTICLE{e101-d_3_602,
author={Masashi TSUCHIDA, Fukuhito OOSHITA, Michiko INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards},
year={2018},
volume={E101-D},
number={3},
pages={602-610},
abstract={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.},
keywords={},
doi={10.1587/transinf.2017FCP0008},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Byzantine-Tolerant Gathering of Mobile Agents in Arbitrary Networks with Authenticated Whiteboards
T2 - IEICE TRANSACTIONS on Information
SP - 602
EP - 610
AU - Masashi TSUCHIDA
AU - Fukuhito OOSHITA
AU - Michiko INOUE
PY - 2018
DO - 10.1587/transinf.2017FCP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2018
AB - 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.
ER -
English
