http://swrc.ontoware.org/ontology#Article
Move-optimal partial gathering of mobile agents in asynchronous trees
en
Distributed system
Mobile agent
Gathering problem
Partial gathering problem
Shibata Masahiro
Ooshita Fukuhito
Kakugawa Hirotsugu
Masuzawa Toshimitsu
Department of Computer Science and Electronics, Kyushu Institute of Technology, 680-4, Kawatsu, Iizuka, Fukuoka, 820-8502, Japan
Graduate School of Information Science, NAIST, 8916-5, Takayama, Ikoma, Nara 630-0192, Japan
Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan
Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan
In this paper, we consider the partial gathering problem of mobile agents in asynchronous tree networks. The partial gathering problem is a generalization of the classical gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g, that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is weaker than that for the (well-investigated) classical gathering problem, and thus, we clarify the difference on the move complexity between them. We consider two multiplicity detection models: weak multiplicity detection and strong multiplicity detection models. In the weak multiplicity detection model, each agent can detect whether another agent exists at the current node or not but cannot count the exact number of the agents. In the strong multiplicity detection model, each agent can count the number of agents at the current node. In addition, we consider two token models: non-token model and removable token model. In the non-token model, agents cannot mark the nodes or the edges in any way. In the removable-token model, each agent initially leaves a token on its initial node, and agents can remove the tokens. Our contribution is as follows. First, we show that for the non-token model agents require Ω(kn) total moves to solve the partial gathering problem, where n is the number of nodes and k is the number of agents. Second, we consider the weak multiplicity detection and non-token model. In this model, for asymmetric trees, by a previous result agents can achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. In addition, for symmetric trees we show that there exist no algorithms to solve the partial gathering problem. Third, we consider the strong multiplicity detection and non-token model. In this model, for any trees we propose an algorithm to achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. At last, we consider the weak multiplicity detection and removable-token model. In this model, we propose an algorithm to achieve the partial gathering in O(gn) total moves. Note that in this model, agents require Ω(gn) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves.
Theoretical Computer Science
705
9-30
2017-09-27
Elsevier
0304-3975
AA00862688
info:doi/10.1016/j.tcs.2017.09.016
Copyright (c) 2017 The Authors. Published by Elsevier B.V.
This is an open access article under the CC BY license
http://creativecommons.org/licenses/by/4.0/
https://doi.org/10.1016/j.tcs.2017.09.016|https://doi.org/10.1016/j.tcs.2017.09.016
Journal Article