Partial Gathering of Mobile Agents in Arbitrary Networks

Masahiro SHIBATA  Daisuke NAKAMURA  Fukuhito OOSHITA  Hirotsugu KAKUGAWA  Toshimitsu MASUZAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.444-453
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0008
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
distributed system,  mobile agent,  gathering problem,  partial gathering problem,  

Full Text: PDF(769.9KB)
>>Buy this Article


Summary: 
In this paper, we consider the partial gathering problem of mobile agents in arbitrary networks. The partial gathering problem is a generalization of the (well-investigated) total 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 no stronger than that for the total gathering problem, and thus, we clarify the difference on the move complexity between them. First, we show that agents require Ω(gn+m) total moves to solve the partial gathering problem, where n is the number of nodes and m is the number of communication links. Next, we propose a deterministic algorithm to solve the partial gathering problem in O(gn+m) total moves, which is asymptotically optimal in terms of total moves. Note that, it is known that agents require Ω(kn+m) total moves to solve the total gathering problem in arbitrary networks, where k is the number of agents. Thus, our result shows that the partial gathering problem is solvable with strictly fewer total moves compared to the total gathering problem in arbitrary networks.