A Distributed Spanning Tree Algorithm
Karl Erik Johansen, Ulla Lundin Jørgensen, Svend Hauge Nielsen, Søren Erik Nielsen, Sven Skyum · DAIMI Report Series · 1987
We present a distributed algorithm for constructing a spanning tree for connected undirected graphs. Nodes correspond to processors and edges correspond to two-way channels. Each processor has initially a distinct identity and all processors perform the same algorithm. Computation as well as communication is asynchronous. The total number of messages sent during a construction of a spanning tree is at most 2E+3NlogN. The maximal message size is loglogN+log(maxid)+3, where maxid is the maximal processor identity.