Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Algorithms for Partial Gathering of Mobile Agents in Asynchronous Rings
verfasst von : Masahiro Shibata, Shinji Kawai, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem requires, for a given input
g
, that each agent should move to a node and terminates so that at least
g
agents should meet at the same node. The requirement for the partial gathering is weaker than that for the ordinary (total) gathering, and thus, we have interests in clarifying the difference on the move complexity between them. We propose two algorithms to solve the partial gathering problem. One algorithm is deterministic and assumes unique ID of each agent. The other is randomized and assumes anonymous agents. The deterministic (resp., randomized) algorithm achieves the partial gathering in
O
(
gn
) (resp., expected
O
(
gn
+
n
log
k
)) total number of moves where
n
is the ring size and
k
is the number of agents, while the total gathering requires Ω(
kn
) moves. We show that the move complexity of the deterministic algorithm is asymptotically optimal.