For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Self-Stabilizing Agent Traversal on Tree Networks
Yoshihiro NAKAMINAMI Toshimitsu MASUZAWA Ted HERMAN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/12/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Distributed Cooperation and Agents
agent traversal, tree, self-stabilization,
Full Text: PDF>>
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 O(Δn) 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 O(Δn) for a tree network on an asynchronous model. The protocols are proved to be asymptotically optimal with respect to the agent traversal time.