The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -