Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 47
Текст из файла (страница 47)
In theasynchronous setting, the breadth-rst spanning tree is not as usable, since we don't knowwhen the construction is complete. We can still do broadcast-convergecast reasonably eciently, on an arbitrary (not necessarily breadth-rst) spanning tree.First we consider how to construct an arbitrary spanning tree. The distinguished sourcenode i0 begins by sending out report messages to all its neighbors. Any other node, uponreceipt of its rst report message, marks itself as done, identies the sender j as its parent,sends a parent i(j ) announcement to the outside world, and sends out report messages onits outgoing links.
The node ignores additional report messages. This idea works ne asynchronously: nodes know when they are done, O(E ) messages are used, and it takes O(diam )time until termination. (There are no pileups on links since only two messages ever get senton each edge, one in each direction.)Now we proceed to the task of broadcasting a message to all nodes. We can construct anarbitrary spanning tree as above, and then i0 uses it to send messages over the tree links.To do this, nodes need to be informed as to which other nodes are their children, and thisrequires local communication from children to parents upon discovery.
Note the interestingtiming anomaly here: tree paths could take (n) time to traverse the second time. To avoidthat, we can send the message in the course of building the tree, by \piggybacking" themessage on all report messages.We can also use an asynchronously-constructed spanning tree to \fan in" results of acomputation back to i0: as in the synchronous case, each node waits to hear from all itschildren in the spanning tree, and then forwards a message to its parent.This brings us to the task of broadcast and convergecast.
Now suppose we want tobroadcast a message and collect acknowledgments (back at i0) that everyone has received it.To solve this problem we do a combination of the asynchronous spanning tree construction237above, followed (asynchronously) by fanning in results from the leaves.In fact, if the tree is being constructed solely for the purpose of sending and getting\acks" for a particular message, it is possible to delete the tree information after fanning in238State:msg , for the value being broadcast, at i0 initially the message it is sending, elsewherenilsend , buer for outgoing messages, at i0 initially contains (bcast m) to all neighbors ofi0 , elsewhere parent , pointer for the parent edge, initially nilacked , a set to keep track of children that have acked, everywhere initially done , Boolean ag, initially falseActions:send action: as usual, just sends anything in send buer.receive (bcast m)Eect: if msg = nil thenmsg mparent jfor all k 2 neighbors ; fj g, put message (bcast m) in sendacked else put message (ack ) to j in sendj ireceive (ack )Eect: acked acked fj gj inish (for i 6= i0)Precondition: acked = neighbors ; fparent gdone = falseEect: put ack message to parent in senddone trueinish (for i = i0)Precondition: acked = neighborsdone = falseEect: output done message to outside worlddone trueiFigure 19.1: Code for the broadcast-convergecast task, without deleting the tree239the results back to the parent.
However, we have to be careful that the node doesn't forgeteverything | since if it later gets a report message from another part of the tree whoseprocessing is delayed, it should \know enough" to ignore it. In other words, we need to keepsome kind of ag at each node saying that it's done. The code is given in Figure 19.1.Analysis. Communication is simple: it takes O(E ) messages to set up the tree, and afterthe tree is set up, it's only O(n) messages to do the broadcast-convergecast work. The timeanalysis is trickier.
One might think that in O(diam ) time the algorithm terminates, sincethat's how long it takes to do the broadcast. The convergecast, however, can take longer.Specically, we have the following timing anomaly: a message can travel fast along a longnetwork path, causing a node to become attached to the spanning tree on a long branch,even though there is a shorter path to it. When the response travels back along the longpath, it may now take time proportional to the length of the path, which is (n) for generalgraphs. To x this problem, we shall need new ideas, such as a synchronizer, which we shalldiscuss next lecture.Example: application to leader election.
The broadcast-convergecast algorithm pro-vides an easy solution to the leader election problem. Recall that the simple leader electionalgorithm we mentioned above didn't terminate. Now, we could do an alternative leaderelection algorithm as follows. Starting from every node, run broadcast-convergecast in parallel, while collecting the maximum ID in the convergecast on each tree. The node that ndsthat the maximum is equal to its own UID gets elected.19.2 Minimum Spanning Tree19.2.1 Problem StatementNow we return to the problem of constructing a minimum-weight spanning tree (MST), thistime in an asynchronous network. Let us recall the problem denition. We are given anundirected graph G = (V E ) with weighted edges, such that each vertex is associated withits own process, and processes are able to communicate with each other via messages sentover edges. We wish to have the processes (vertices) cooperate to construct a minimumweight spanning tree for the graph G.
That is, we want to construct a tree covering thevertices in G, whose total edge weight is less than or equal to that of every other spanningtree for G.We assume that processes have unique identiers, and that each edge of the graph isassociated with a unique weight known to the vertices on each side of that edge. (The240assumption of unique weights on edges is not a strong one, given that processes have uniqueidentiers: if edges had non-distinct weights, we could derive \virtual weights" for all edgesby appending the identier numbers of the end points onto the edge weights, and use themas tie-breakers between the original weights.) We will also assume that a process does notknow the overall topology of the graph | only the weights of its incident edges | and thatit can learn non-local information only by sending messages to other processes over thoseedges.
The output of the algorithm will be a \marked" set of tree edges every process willmark those edges adjacent to it that are in the nal MST.There is one signicant piece of input to this algorithm: namely, that any number of nodeswill be \awakened" from the outside to begin computing the spanning tree. A process canbe awakened either by the \outside world" (asking that the process begin the spanning treecomputation), or by another (already-awakened) process during the course of the algorithm.The motivation for the MST problem comes mainly from the area of communications.The weights of edges might be regarded as \message-sending costs" over the links betweenprocessess.
In this case, if we want to broadcast a message to every process, we would usethe MST to get the message to every process in the graph at minimum cost.19.2.2 Connections Between MST and Other ProblemsThe MST problem has strong connections to two other problems: that of nding any (undirected, unrooted) spanning tree at all for a graph, and that of electing a leader in a graph.If we are given an (undirected, unrooted) spanning tree, it is pretty easy to elect a leaderthis proceeds via a \convergecast" of messages from the leaves of the tree until the incomingmessages converge at some particular node, which can then be designated as the leader. (Itis possible that the messages converge at some edge rather than some node, in which caseone of the endpoints of this edge, say the one with the larger ID, can be chosen.)Conversely, if we are given a leader, it is easy to nd an arbitrary spanning tree, asdiscussed above (under broadcast-convergecast): the leader just broadcasts messages alongeach of its neighboring edges, and nodes designate as their parent in the tree that nodefrom which they rst receive an incoming message (after which the nodes then broadcasttheir own messages along their remaining neighboring edges).
So, modulo the costs of thesebasic algorithms, the problems of leader election and nding an arbitrary spanning tree areequivalent.A minimum spanning tree is of course a spanning tree. The converse problem, going froman arbitrary spanning tree (or a leader) to a minimum spanning tree, is much harder.One possible idea would be to have every node send information regarding its surroundingedges to the leader, which then computes the MST centrally and distributes the information241back to every other node in the graph. This centralized strategy requires a considerableamount of local computation, and a fairly large amount of communication.19.2.3 The Synchronous Algorithm: ReviewLet us recall how the synchronous algorithm worked.
It was based on two basic propertiesof MST's:Property 1 Let G be an undirected graph with vertices V and weighted edges E . Let(Vi Ei ) : 1 i k be any spanning forest for G, with k > 1. Fix any i, 1 i k. Let ebe an edge of lowest cost in in the set fe0 : e0 2 E ; Sj Ej and exactly one endpoint of e' isSin Vi g. Then there is a spanning tree for G that includes feg ( j Ej ) and this tree is of aslow a cost as any spanning tree for G that includes Sj Ej .Property 2 If all edges of a connected graph have distinct weights, then the MST is unique.These properties justify a basic strategy in which the MST is built up in fragments asfollows.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
