MAINTENANCE OF A SPANNING TREE FOR DYNAMIC GRAPHS BY MOBILE AGENTS AND LOCAL COMPUTATIONS

摘要

The problem of constructing and maintaining a spanning tree in dynamic networks is important in distributed systems. Trees are essential structures in various communication protocols such as information broadcasting, routing, etc. In a distributed computing environment, the solution of this problem has many practical motivations. To make designing distributed algorithm easier, we model this latter with a local computation model. Based on the mobile agent paradigm, we present in this paper a distributed algorithm that maintain a hierarchical spanning tree in dynamic networks. We study all topological events that may affect the structure of the spanning tree: we address the appearance and the disappearance of places and communication channels.