Self-Stabilizing Agent Traversal on Tree Networks

Yoshihiro NAKAMINAMI; Toshimitsu MASUZAWA; Ted HERMAN

Self-Stabilizing Agent Traversal on Tree Networks

Yoshihiro NAKAMINAMI, Toshimitsu MASUZAWA, Ted HERMAN

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E87-D No.12 pp.2773-2780

Publication Date: 2004/12/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Distributed Cooperation and Agents

Cite this

Copy

Yoshihiro NAKAMINAMI, Toshimitsu MASUZAWA, Ted HERMAN, "Self-Stabilizing Agent Traversal on Tree Networks" in IEICE TRANSACTIONS on Information, vol. E87-D, no. 12, pp. 2773-2780, December 2004, doi: .
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. 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e87-d_12_2773/_p

Copy

@ARTICLE{e87-d_12_2773,
author={Yoshihiro NAKAMINAMI, Toshimitsu MASUZAWA, Ted HERMAN, },
journal={IEICE TRANSACTIONS on Information},
title={Self-Stabilizing Agent Traversal on Tree Networks},
year={2004},
volume={E87-D},
number={12},
pages={2773-2780},
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. 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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Self-Stabilizing Agent Traversal on Tree Networks
T2 - IEICE TRANSACTIONS on Information
SP - 2773
EP - 2780
AU - Yoshihiro NAKAMINAMI
AU - Toshimitsu MASUZAWA
AU - Ted HERMAN
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2004
AB - 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.
ER -