Weakly Byzantine Gathering with a Strong Team

Jion HIROSE; Junya NAKAMURA; Fukuhito OOSHITA; Michiko INOUE

doi:10.1587/transinf.2021FCP0011

IEICE TRANSACTIONS on Information

Weakly Byzantine Gathering with a Strong Team

Jion HIROSE, Junya NAKAMURA, Fukuhito OOSHITA, Michiko INOUE

Full Text Views

0

Cite this

Summary :

We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n⁴·|Λ_good|·X(n)) rounds, where |Λ_good| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f²+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambda_good|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambda_all|)·X(N)) rounds, where |&Lambda_all| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambda_all|=O(|&Lambda_good|) holds.

Publication: IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.541-555

Publication Date: 2022/03/01

Publicized: 2021/10/11

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2021FCP0011

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)

Category

Authors

Jion HIROSE
  Nara Institute of Science and Technology
Junya NAKAMURA
  Toyohashi University of Technology
Fukuhito OOSHITA
  Nara Institute of Science and Technology
Michiko INOUE
  Nara Institute of Science and Technology

Keyword

distributed algorithm, deterministic algorithm, mobile agents, gathering, Byzantine faults

Cite this

Copy

Jion HIROSE, Junya NAKAMURA, Fukuhito OOSHITA, Michiko INOUE, "Weakly Byzantine Gathering with a Strong Team" in IEICE TRANSACTIONS on Information, vol. E105-D, no. 3, pp. 541-555, March 2022, doi: 10.1587/transinf.2021FCP0011.
Abstract: We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n⁴·|Λ_good|·X(n)) rounds, where |Λ_good| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f²+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambda_good|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambda_all|)·X(N)) rounds, where |&Lambda_all| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambda_all|=O(|&Lambda_good|) holds.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0011/_p

Copy

@ARTICLE{e105-d_3_541,
author={Jion HIROSE, Junya NAKAMURA, Fukuhito OOSHITA, Michiko INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Weakly Byzantine Gathering with a Strong Team},
year={2022},
volume={E105-D},
number={3},
pages={541-555},
abstract={We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n⁴·|Λ_good|·X(n)) rounds, where |Λ_good| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f²+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambda_good|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambda_all|)·X(N)) rounds, where |&Lambda_all| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambda_all|=O(|&Lambda_good|) holds.},
keywords={},
doi={10.1587/transinf.2021FCP0011},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Weakly Byzantine Gathering with a Strong Team
T2 - IEICE TRANSACTIONS on Information
SP - 541
EP - 555
AU - Jion HIROSE
AU - Junya NAKAMURA
AU - Fukuhito OOSHITA
AU - Michiko INOUE
PY - 2022
DO - 10.1587/transinf.2021FCP0011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n⁴·|Λ_good|·X(n)) rounds, where |Λ_good| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f²+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambda_good|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambda_all|)·X(N)) rounds, where |&Lambda_all| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambda_all|=O(|&Lambda_good|) holds.
ER -

IEICE TRANSACTIONS on Information