Gathering with a strong team in weakly Byzantine environments
share
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^4·|Λ_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^2+9f+4 agents exist. Both the algorithms take the upper bound N of n as input. The first algorithm achieves gathering with non-simultaneous termination in O((f+|Λ_good|)· X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|Λ_all|)· X(N)) rounds, where |Λ_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 |Λ_all|=O(|Λ_good|) holds.
READ FULL TEXT