A simple algorithm for computing minimum spanning trees in the Internet

A central problem in wide-area networks is to efficiently multicast a message to all members (hosts) of a target group. One of the most effective methods to multicast a message is to send the message along the edges of a spanning tree connecting all the members of the group. In this paper, we propose a new fully distributed algorithm to build a minimum spanning tree (MST) in a generic communication network. During the execution, the algorithm maintains a collection of disjoint trees spanning all the group members. Every tree, which initially consists of only one node, independently expands by joining the closest tree, until all of the nodes are connected in a single tree. The resulting communication topology is both robust (there are no singularities subject to failures) and scalable (every node stores a limited amount of local information that is independent of the size of the network). (C) Elsevier Science Inc. 1997.