Self-Stabilizing Agent Traversal
Ted Herman6
and Toshimitsu Masuzawa7 
| (6) |
University of Iowa, USA |
| (7) |
Osaka University, Japan |
Abstract
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. It is shown for
a tree network and a synchronous model that this problem has O(Δn) upper and lower time bounds where Δ is the maximum degree of any vertex in the communication network. The synchronous algorithm
is selfstabilizing and can also be used for an asynchronous system. A second algorithm is presented and analyzed to show O(n) round complexity for the case of a line of n asynchronous processes.
Research supported by NSF award CAREER 97-9953 and DARPA contract F33615- 01-C-1901.
This work is supported in part by Japan Society for the Promotion of Science (JSPS), Grant-in-Aid for Scientific Research((c)(2)12680349).
References secured to subscribers.