Self-Stabilizing Agent Traversal on Tree Networks(Distributed Cooperation and Agents)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2004-12-01
著者
-
MASUZAWA Toshimitsu
Graduate School of Information Science and Technology, Osaka University
-
Masuzawa Toshimitsu
Graduate School Of Engineering Science Osaka University
-
HERMAN Ted
Department of Computer Science, University of Iowa
-
Herman Ted
Department Of Computer Science University Of Iowa
-
NAKAMINAMI Yoshihiro
Graduate School of Engineering Science, Osaka University
-
Nakaminami Y
Graduate School Of Engineering Science Osaka University
関連論文
- A Self-Adaptive Routing Protocol in Wireless LANs Based on Attractor Selection
- A Biologically Inspired Self-Adaptation of Replica Density Control
- A Message-Efficient Peer-to-Peer Search Protocol Based on Adaptive Index Dissemination
- An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks
- Self-Adaptive Mobile Agent Population Control in Dynamic Networks Based on the Single Species Population Model(Distributed Cooperation and Agents)
- A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
- Timed Atomic Broadcast Resiliet to Multiple Timing Faults
- Timed Atomic Broadcast Resiliet to Multiple Timing Faults
- 木ネットワークにおける自己安定エージェント巡回アルゴリズム
- Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
- Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
- Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
- Distributed Construction Protocols of Probabilistic Degree-Weighted Peer-to-Peer Overlays
- Self-Stabilization in Dynamic Networks
- Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
- Self-Stabilizing Agent Traversal on Tree Networks(Distributed Cooperation and Agents)
- A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance