23-04-2012, 12:22 PM
A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree
A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree.pdf (Size: 405.04 KB / Downloads: 38)
INTRODUCTION
For communication in computer networks, often only a
subset of the available connections is used to communicate
at any given time. If all nodes are connected using the
smallest number of links, the subset forms a spanning tree
of the network. This has economical benefits compared to
using the entire set of available links, assuming that merely
keeping a link active for potentially sending messages induces
some cost. Furthermore, as only one path exists between
any communication pair, a spanning tree simplifies routing
and allows small routing tables. Depending on the purpose
of the network, there is a variety of desirable properties of
a spanning tree. We are interested in a Minimum Diameter
Spanning Tree (MDST), i.e., a tree that minimizes the largest
distance between any pair of nodes, thus minimizing the worst
case length of any transmission path, even if edge lengths are
not uniform.
ALGORITHMIC SETTING AND BASIC IDEA
In our setting, nodes have unique identifiers that possess a
linear order. Each node knows its own neighbors in T and
in G, and for each neighbor the length of the corresponding
edge. At the end of the distributed computation, for every
edge e = (x, p(x)) of T, the selected best swap edge f (if
any exists) must be known to the nodes x and p(x) (but
not necessarily to any other nodes). We assume port-to-port
communication between neighbouring nodes. The distributed
system of nodes is totally asynchronous.
THE PREPROCESSING PHASE
The preprocessing phase serves the purpose of making the
needed terms in the sums described in the previous section
available at the nodes of the tree. Details of this phase can be
found in the pseudocode given as Algorithm Preprocessing
DISCUSSION
We have presented a distributed algorithm for computing all
best swap edges for a minimum diameter spanning tree. Our
solution is asynchronous, requires unique identifiers from a
linearly ordered universe (but only for tiebreaking to determine
a center node), and uses O(kDk) time and O(n¤ + m) small
messages, or O(n) messages of size O(n). It remains an
open problem to extend our approach to subgraphs with other
objectives; for instance, can we efficiently compute swap edges
for failing edges in a spanner?