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
Kami mencadangkan dua algoritma untuk pengumpulan k ejen mudah alih dalam persekitaran Byzantine tak segerak. Untuk kedua-dua algoritma, kami menganggap bahawa topologi graf adalah sewenang-wenangnya, setiap nod dilengkapi dengan papan putih yang disahkan, ejen mempunyai ID unik dan paling banyak. f ejen Byzantine lemah wujud. Di sini, ejen Byzantine yang lemah boleh membuat kelakuan sewenang-wenangnya kecuali memalsukan IDnya. Di bawah andaian ini, algoritma pertama mencapai pengumpulan tanpa pengesanan penamatan dalam O(m+fn) bergerak setiap ejen (m ialah bilangan tepi dan n ialah bilangan nod). Algoritma kedua mencapai perhimpunan dengan pengesanan penamatan dalam O(m+fn) bergerak setiap ejen dengan tambahan mengandaikan bahawa ejen pada nod yang sama disegerakkan, $f k. Untuk pengetahuan terbaik kami, ini adalah kerja pertama untuk menangani masalah pengumpulan ejen mudah alih untuk rangkaian topologi arbitrari dalam persekitaran Byzantine tak segerak.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -