The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nous proposons deux algorithmes pour la collecte de k agents mobiles dans des environnements byzantins asynchrones. Pour les deux algorithmes, nous supposons que la topologie du graphe est arbitraire, que chaque nœud est équipé d'un tableau blanc authentifié, que les agents ont des identifiants uniques et qu'au plus f Il existe des agents faiblement byzantins. Ici, un agent faiblement byzantin peut avoir un comportement arbitraire sauf falsifier son identité. Sous ces hypothèses, le premier algorithme réalise un regroupement sans détection de terminaison dans O(m+fn) se déplace par agent (m est le nombre d'arêtes et n est le nombre de nœuds). Le deuxième algorithme réalise un regroupement avec détection de terminaison en O(m+fn) se déplace par agent en supposant en outre que les agents sur le même nœud sont synchronisés, $f k. À notre connaissance, il s'agit du premier travail à aborder le problème de collecte d'agents mobiles pour des réseaux à topologie arbitraire dans des environnements byzantins asynchrones.
Masashi TSUCHIDA
Nara Institute of Science and Technology
Fukuhito OOSHITA
Nara Institute of Science and Technology
Michiko INOUE
Nara Institute of Science and Technology
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.
Copier
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
Copier
@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},}
Copier
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 -