Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 8

Notice that any acyclicset of edges (i.e., a forest) can be augmented to a spanning tree. The following lemmaindicates which edges can be in a minimum spanning tree.Lemma 1 Let G = (V E ) be an undirected graph, and let f(Vi Ei) : 1 i kg be anyspanning forest for G, where each (Vi Ei ) is connected. Fix any i, 1 i k . Let e be anedge of lowest cost in in the set89<0 0=0 is in V :e:e2E;Eandexactlyoneendpointofeji:jThen there is a spanning tree for G that includes Sj Ej ) and e, and this tree is of as low acost as any spanning tree for G that includes Sj Ej .Proof: By contradiction.Suppose the claim is false | i.e., that there exists a spanningStree T that contains j Ej , does not contain e, and is of strictly lower cost than any other37111Figure 3.2: the circles represent components.

If the components choose MWOE as depicted bythe arrows, a cycle would be created.spanning tree which contains feg Sj Ej . Now, consider the graph T 0 obtained by adding eto T . Clearly, T 0 contains a cycle, which has one more edge e0 6= e which is outgoing fromVi .By the choice of e, we know that weight (e0) weight (e ).

Now, consider T constructedby deleting e0 from T 0. T is spanning tree for G, it contains feg Sj Ej , and it has weightno greater than that of T , a contradiction.The lemma above suggests a simple strategy for constructing a spanning tree: start withthe trivial spanning forest that contains no edges then, for some connected component, addthe minimal-weight outgoing edge (MWOE). The claim that we have just proven guaranteesthat we are safe in adding these edges: there is an MST that contains them. We can repeatthis procedure until there is only one connected component, which is an MST. This principleforms the basis for well-known sequential MST algorithms.

The Prim-Dijkstra algorithm,for instance, starts with one node and successively adds the smallest-weight outgoing edgefrom the current (partial) tree until a complete spanning tree has been obtained. TheKruskal algorithm, as another example, starts with all nodes as \fragments" (i.e., connectedcomponents of the spanning forest) and successively extends each fragment with the minimunweight outgoing edge, thus combining fragments until there is only one fragment, which isthe nal tree.

More generally, we could use the following basic strategy: start with all nodesas fragments and successively extend an arbitrary fragment with its MWOE, combiningfragments where possible.It is not readily clear whether we can do this in parallel. The answer, in general, isnegative. Consider, for example, the graph in Figure 3.2.However, if all the edges have distinct weights, then there is no problem, as implied byfollowing lemma.Lemma 2 If all edges of a graph G have distinct weights, then there is exactly one MST forG.Proof: Similar to the proof of Lemma 1 left as an exercise.By Lemma 1, if we have a forest all of whose edges are in the unique MST, then all38Figure 3.3: arrows represent MWOEs.

Exactly one edge is chosen twice in each new component.MWOE's for all components are also in the unique MST. So we can add them all in at once,in parallel, and there is no danger of creating a cycle. So all we have to worry about ismaking the edge weights unique: this is easily done using the UIDs. The weight of an edge(i j ) will, for our purposes, be the triplet (weight vi vj ), where vi < vj , and vi (resp., vj )denotes the UID of node i (resp., j ). The order relation among the edges is determined bythe lexicographical order among the triplets.Using Lemma 2 and the UIDs as described above, we can now sketch an algorithm fordistributed construction of MST. The algorithm builds the component in parallel, in \levels"as follows. It is based on the asynchronous algorithm of Gallager, Humblet and Spira.Start with Level 0 components consisting of individual nodes, and no edges.Suppose inductively that we have Level i components, each with its own spanningtree of edges established, and with a known leader within the component.

Toget the Level i + 1 components, each Level i component will conduct a searchalong its spanning tree nodes, for the MWOE of the component. Specically, theleader broadcasts search requests along tree edges. Each node must nd its ownMWOE | this is done by broadcasting along all non-tree edges to see whetherthe other end is in same component or not. (This can be checked by comparingthe leader's UID, which is used at all the nodes of a component as the componentUID.) Then, the nodes convergecast the responses toward the leader, while takingminimums along the way.When all components have found their MWOE's, the fragments are merged byadding the MWOE's in | the leader can communicate with the source of theMWOE to tell it to mark the edge.

Finally, a new leader must be chosen. Thiscan be done as follows. It is easy to see that for each new connected component,there is a unique new edge that is MWOE of both endpoint components (thisis the edge with the least weight among all the new edges). See Figure 3.3 forexample. We can let new leader be the larger UID endpoint of this edge.39Note that it is crucial to keep the levels synchronized: so when a node inquires if theother endpoint of a candidate edge is in the same component or not, the other endpoint hasup-to-date information. If the UID at the other end is dierent, we want to be sure thatthe other end is really in a dierent component, and not just that it hasn't received thecomponent UID yet.Therefore, we execute the levels synchronously, one at a time.

To be sure we havecompleted a level before going on to the next, we must allow an overestimate of time (which,unfortunately, can be big). The time for a level can be #(n), in the worst case. (Not O(diam ){ the paths on which communication takes place are not necessarily minimum in terms ofnumber of links.) The number of levels is bounded by log n, since number of components isreduced by at least a half at each level.We conclude that the time complexity is O(n log n). The message complexity is O((n +E ) log n), since in each level O(n) messages are sent along all the tree edges, and O(E )additional messages are required to do the exploration for local MWOE's.Remark : The number of messages can be reduced to O(n log n + jE j) by being moreclever about the local MWOE search strategy. The optimization makes the time increaseby at most O(n) time units.

The idea is as follows. Each node marks the edges when theyare known to be in same component | there is no need to \explore" them again. Also, theedges are explored in order, one at a time, starting from the lightest. This way each edgeis either marked or discovered to be the local MWOE. For the message complexity analysis,we note that the number of messages sent over tree edges is, as before, O(n log n). Let usapportion the cost of explore messages. Each edge gets explored and rejected at most oncein each direction, for a total of O(jE j). There can be repeated exploration of edges that getlocally accepted (i.e., are found to be outgoing), but there is at most one such explorationper node in each level, summing up for a total of O(n log n).3.3 Maximal Independent SetSo far, we saw a collection of basic synchronous network algorithms, motivated by graphtheory and practical communications.

We shall now see one more example, before goingto study models with failures, that of nding a Maximal Independent Set of the nodes of agraph.This problem can be motivated by resource allocation problems in a network. The neighbors in the graph represent processes than cannot simultaneously perform some activityinvolving a shared resource (such as radio broadcast). It is undesirable to have a processblocked if no neighbors are broadcasting, hence the maximality requirement.40The following algorithm, due to Luby, is particularly interesting because is simple andbasic, and because it introduces the use of randomization.Problem Statement. Let G = (V E ) be a undirected graph. A set I V of nodes isindependent if for all nodes i j 2 I , (i j ) 2= E . An independent set I is maximal if any set I 0which strictly contains I is not independent. Our goal is to compute a maximal independentset of G.

The output is done by each member of I eventually sending a special message in-I.We assume that a bound B on n, the number of nodes, is known to all the nodes. Wedo not need to assume the existence of UID's | i.e., we assume an \anonymous" network.The Algorithm. The basic underlying strategy is based on the following iterative scheme.Let G = (V E ) be the initial graph.I := while V 6= dochoose a set I 0 V that is independent in GI := I I 0G := induced subgraph of G on V ; I 0 ; nbrs (I 0)end whileThis scheme always produces a maximal independent set: by construction, I is independent, and we throw out neighbors of G any element put into I maximality is also easy, sincethe only nodes that are removed from consideration are neighbors of nodes inserted into I .The key question in implementing this general \skeleton" algorithm is how to choose I 0at each iteration.