A distributed spanning tree algorithm for topology-aware networks

Abstract. A topology-aware network is a dynamic network in which the nodes can detect whether locally topology changes occur. Many modern networks, like IEEE 1394.1, are topology-aware networks. We present a distributed algorithm for computing and maintaining an arbitrary spanning tree in such a topology-aware network. Although usually minimal spanning trees are studied, in practice arbitrary spanning trees are often sufficient. Since our algorithm is not involved in the detection of topology changes, it performs better than the spanning tree algorithms in standards like IEEE 802.1. Because reasoning about distributed algorithms is rather tricky, we use a systematic approach to prove our algorithm.