Finding Spanning Forests by Broadcasting

摘要

We consider the problem of finding a spanning forest of a graph by distributed algorithms. If the input graph is weighted, then the goal is to find a minimum-weight spanning forest. The input is distributed among the processors in such a way that each edge is held by one processor. We also consider an adversarial model, in which an adversary controls the timing of obtaining inputs by processors. The processors communicate by broadcasting. The goal is to have the edges of a spanning forest broadcast on the network. The underlying broadcast network is implemented as a multiple-access channel. We study the optimality of algorithmic solutions, which may depend on the class of algorithms. We consider deterministic versus randomized algorithms, and adaptive versus oblivious ones. We also prove lower bounds, that either justify the optimality of specific algorithms, or show that optimal performance depends on the class of algorithms.