A distributed spanning tree algorithm

Authors: Karl Erik Johansen Ulla Lundin Jørgensen Svend Hauge Nielsen Søren Erik Nielsen Sven Skyum

Publish Date: 1987/7/8

Volume: , Issue: , Pages: 1-12

PDF Link

Abstract

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 asyncronous The total number of messages sent during a construction of a spanning tree is at most 2E+3NlogN The maximal message size is loglogN+logmaxid+3 where maxid is the maximal processor identity

Keywords: