We introduce a recursive (“anytime”) distributed algorithm that iteratively restructures any initial spanning tree of a weighted graph towards a minimum spanning tree while guaranteeing at each successive step a spanning tree shared by all nodes that is of lower weight than the previous. Each recursive step is computed by a different active node at a computational cost at most quadratic in the total number of nodes and at a communications cost incurred by subsequent broadcast of the new edge set over the new spanning tree. We show that a polynomial cubic in the number of nodes bounds the worst case number of such steps required to reach a minimum spanning tree and, hence, the number of broadcasts along the way. We conjecture that the distributed, anytime nature of this algorithm is particularly suited to tracking minimum spanning trees in (sufficiently slowly changing) mobile ad hoc networks.
a subsidiary of the Penn Engineering GRASP Lab