Distributed communication complexity of spanning tree construction

We consider the problem of constructing a spanning tree in a synchronized network with an unknown topology. We give lower and upper bounds on the complexity of protocols for spanning tree constriction in various settings: for deterministic and probabilistic protocols, networks with distinguishable nodes, and anonymous networks. We present suboptimal protocols for which the multiplicative gap from the lower bound can be an arbitrarily slowly growing function of the number of vertices in the network.