A distributed algorithm for minimum-weight spanning trees

A distributed algorithm is presented that constructs the minimum weight spanning tree in a connected undirected graph with distinct edge weights. A processor exists at each node of the graph, knowing initially only the weights of the adjacent edges. The processors obey the same algorithm and exchange messages with neighbors until the tree is con-structed. The total number of messages required for a graph of N nodes and E edges is at most 5N log2 N + 2E and a message contains at most one edge weight plus log2 8N bits. The algorithm can be initiated spontaneous-ly at any node or at any subset of nodes. tThis research was conducted at the M.I.T. Laboratory for Information an