Self-Stabilizing Agent Traversal on Tree Networks
-
- NAKAMINAMI Yoshihiro
- Graduate School of Engineering Science, Osaka University
-
- MASUZAWA Toshimitsu
- Graduate School of Engineering Science, Osaka University
-
- HERMAN Ted
- Department of Computer Science, University of Iowa
Search this article
Description
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 selfstabilizing 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.
Journal
-
- IEICE Transactions of Inf & Systems, D
-
IEICE Transactions of Inf & Systems, D 87 (12), 2773-2780, 2004-12-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1571980077395714048
-
- NII Article ID
- 110003213887
-
- NII Book ID
- AA10826272
-
- ISSN
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- CiNii Articles