Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks

Details Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks

2009-04-20

arxiv.org/abs/0904.3087v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

This paper investigates the problem of building and maintaining distributed spanning trees in dynamic networks. Contrarily to previous solutions, we do not assume the existence of stabilization periods between topological changes, and address the more general case where such changes may occur at anytime and disconnect the network. Hence, we present an algorithm that relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of spanning trees, using random walks of tokens. The original idea behind this algorithm is simple: each tree in the forest hosts exactly one token, whose circulation is strictly limited to the edges of the tree. When two tokens meet, the trees are merged and one of the two tokens is destroyed. When a link is broken, the adjacent node, belonging to the token-free tree, generates a new token. The main features of this approach are that both mergings and splittings are purely localized phenomenon, which allow a transparent and continuous use of the involved subtrees (as far as no higher-level communication is concerned). The algorithm presented here, while briefly introduced in another context, was never analyzed nor properly discussed. We do both here, and provide analytical expressions of the expected merging time of two given trees. We finally propose a substantial optimization to the algorithm that consists in using a memory-based bias in the token walks. The impact of this optimization is investigated both analytically and experimentally.

Affiliated with

Also associated with

No associations

Rating

Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-174651