Self-Stabilizing Agent Traversal on Tree Networks

Yoshihiro NAKAMINAMI  Toshimitsu MASUZAWA  Ted HERMAN  

IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.12   pp.2773-2780
Publication Date: 2004/12/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Distributed Cooperation and Agents
agent traversal,  tree,  self-stabilization,  

Full Text: PDF>>
Buy this Article

This paper introduces the problem of n mobile agents that repeatedly visit all n nodes of a given network, subject to the constraint that no two agents can simultaneously occupy a node. This paper first presents a self-stabilizing phase-based protocol for a tree network on a synchronous model. The protocol realizes agent traversal with On) time where n is the number of nodes and Δ is the maximum degree of any vertex in the communication network. The phase-based protocol can also be applied to an asynchronous model and a ring network. This paper also presents a self-stabilizing link-alternator-based protocol with agent traversal time of On) for a tree network on an asynchronous model. The protocols are proved to be asymptotically optimal with respect to the agent traversal time.