Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks

Free registration required

Executive Summary

This paper investigates the problem of building and maintaining distributed spanning trees in dynamic networks. Contrarily to previous solutions, the authors 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, they 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.

  • Format: PDF
  • Size: 125.66 KB