Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Self-Stabilizing Agent Traversal

Ted HermanContact Information and Toshimitsu MasuzawaContact Information

(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 On) 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).

Contact Information Ted Herman
Email: herman@cs.uiowa.edu

Contact Information Toshimitsu Masuzawa
Email: masuzawa@ics.es.osaka-u.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)