  Highly dynamic networks are characterized by frequent changes in the
availability of communication links. These networks are often partitioned into
several components, which split and merge unpredictably. We present a
distributed algorithm that maintains a forest of (as few as possible) spanning
trees in such a network, with no restriction on the rate of change. Our
algorithm is inspired by high-level graph transformations, which we adapt here
in a (synchronous) message passing model for dynamic networks. The resulting
algorithm has the following properties: First, every decision is purely
local---in each round, a node only considers its role and that of its neighbors
in the tree, with no further information propagation (in particular, no wave
mechanisms). Second, whatever the rate and scale of the changes, the algorithm
guarantees that, by the end of every round, the network is covered by a forest
of spanning trees in which 1) no cycle occur, 2) every node belongs to exactly
one tree, and 3) every tree contains exactly one root (or token). We primarily
focus on the correctness of this algorithm, which is established rigorously.
While performance is not the main focus, we suggest new complexity metrics for
such problems, and report on preliminary experimentation results validating our
algorithm in a practical scenario.
