Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 49
Текст из файла (страница 49)
Since we are assuming that the edges have unique weights,the weights could be the identiers.We now want to show that this strategy, of having fragments merge together and absorbthemselves into larger fragments, will in fact suce to combine all fragments into a MST forthe entire graph.Claim 1 If we start from an initial situation in which each fragment consists of a singlenode, and we apply any possible sequence of merge and absorb steps, then there is alwayssome applicable step to take until the result is a single fragment containing all the nodes.Proof: We want to show that no matter what conguration we arrive at in the course ofthe algorithm, there is always some merge or absorb step that can be taken.One way to see that this is true is to look at all the current fragments at some stagein the running algorithm.
Each of these fragments will identify its MWOE leading to someother fragment. If we view the fragments as vertices in a \fragment-graph," and draw theMWOE for each fragment, we get a directed graph with an equal number of vertices andedges (see Figure 19.4). Since we have k nodes and k edges (for some k), such a directedgraph must have a cycle and because the edges have distinct weights, only cycles of size2 (i.e., cycles involving two fragments) may exist. Such a 2-cycle represents two fragmentsthat share a single MWOE.Now, it must be the case that the two fragments in any 2-cycle can be combined. If thetwo fragments in the cycle have the same level number, a merge operation can take placeotherwise, the fragment with the smaller level number can absorb itself into the fragment246 -?--Figure 19.4: A collection of fragments and their minimum-weight outgoing edges.with the larger one.Let's return to the question of how the MWOE is found for a given fragment.
The basicstrategy is as follows. Each node in the fragment is nds its own MWOE leading outsidethe fragment then the information from each node is collected at a selected process, whichtakes the minimum of all the edges suggested by the individual nodes.This seems straightforward, but it re-opens the question of how a node knows that agiven edge is outgoing|that is, that the node at the other end of the edge lies outside thecurrent fragment. Suppose we have a node p that \looks across" an edge e to a node q atthe other end. How can p know if q is in a dierent fragment or not?A fragment name (or identier) may be thought of as a pair (core level ). If q's fragmentname is the same as p's, then p certainly knows that q is in the same fragment as itself.However, if q's fragment name is dierent from that of p, then it is still possible that q andp are indeed in the same fragment, but that q has not yet been informed of that fact.
Thatis to say, q's information regarding its own current fragment may be out of date.However, there is an important fact to note: if q's fragment name has a core unequal tothat of p, and it has a level value at least as high as p, then q can't be in the fragment thatp is in currently, and never will be. This is so because in the course of the algorithm, a nodewill only be in one fragment at any particular level.
Thus, we have a general rule that qcan use in telling p whether both are in the same fragment: if the value of (core level ) forq is the same as that of p then they are in the same fragment, and if the value for core isdierent for q and the value of level is at least as large as that of p then they are in dierentfragments.The upshot of this is that MWOE(p) can be determined only if level (q) level (p). If qhas a lower level than p, it simply delays answering p until its own level is at least as greatas p's.247q '&q $%F p- q F0Figure 19.5: Fragment F absorbs itself into F 0 while F 0 is still searching for its own MWOE.However, notice that we now have to reconsider the progress argument, since this extraprecondition may cause progress to be blocked.
Since a fragment can be delayed in ndingits MWOE (since some individual nodes within the fragment are being delayed), we mightask whether it is possible for the algorithm to reach a state in which neither a merge orabsorb operation is possible. To see that this is not the case, we use essentially the sameargument as before, but this time we only consider those MWOE's found by fragmentswith the lowest level in the graph (call this level l).
These succeed in all their individualMWOE(p) calculations, so succeed in determining their MWOE for the entire fragment.Then the argument is as before: If any fragment at level l nds a MWOE to a higher-levelfragment, then an absorb operation is possible and if every fragment at the level l has aMWOE to some other fragment at level l, then we must have a 2-cycle between two fragmentsat level l, and a merge operation is possible. So again, even with the new preconditions, weconclude that the algorithm must make progress until the complete MST is found.Getting back to the algorithm, each fragment F will nd its overall MWOE by taking aminimum of the MWOE for each node in the fragment. This will be done by a \broadcastconvergecast" algorithm starting from the core, emanating outward, and then collecting allinformation back at the core.This leads to yet another question: what happens if a \small" fragment F gets absorbedinto a larger one F 0 while F 0 is still in the course of looking for its own MWOE?There are two cases to consider (consult Figure 19.5 for the labeling of nodes).
Supposerst that the minimum edge leading outside the fragment F 0, has not yet been determined.In this case, we search for a MWOE for the newly-augmented fragment F 0 in F as well (thereis no reason it cannot be there).On the other hand, suppose MWOE(F 0) has already been found at the time that Fabsorbs itself into F 0. In that event, the MWOE for q cannot possibly be e, since the only248way that the MWOE for q could be known is for that edge to lead to a fragment with a levelat least as great as F 0, and we know that the level of F is smaller than that of F 0. Moreover,the fact that the MWOE for q is not e implies that the MWOE for the entire fragmentF 0 cannot possibly be in F .
This is true because e is the MWOE for fragment F , andthus there can be no edges leading out of F with a smaller cost than the already-discoveredMWOE for node q. Thus, we conclude that if MWOE(F 0) is already known at the time theabsorb operation takes place, then fragment F 0 needn't look for its overall MWOE amongthe newly-absorbed nodes. (This is fortunate, since if F 0 did in fact have to look for itsMWOE among the new nodes, it could be too late: by the time the absorb operation takesplace, q might have already reported its own MWOE, and fragment F 0 might already bedeciding on an overall MWOE without knowing about the newly-absorbed nodes.)19.2.6 A Summary of the Code in the GHS AlgorithmWe have described intuitively the major ideas of the Gallager-Humblet-Spira algorithm thisexplanation above should be sucient to guide the reader through the code presented intheir original paper.Although the actual code in the paper is dense and complicated, the possibility of anunderstandable high-level description turns out to be fairly typical for communications algorithms.
In fact, the high-level description that we have seen can serve as a basis for acorrectness proof for the algorithm, using simulations.The following message types are employed in the actual code: INITIATE messages are broadcast outward on the edges of a fragment to tell nodes tostart nding their MWOE. REPORT messages are the messages that carry the MWOE information back in.(These are the convergecast response to the INITIATE broadcast messages.) TEST messages are sent out by nodes when they search for their own MWOE. ACCEPT and REJECT messages are sent in response to TEST messages from nodesthey inform the testing node whether the responding node is in a dierent fragment(ACCEPT) or is in the same fragment (REJECT).
CHANGE-ROOT is a message sent toward a fragment's MWOE once that edge isfound. The purpose of this message is to change the root of the (merging or currentlybeing-absorbed) fragment to the appropriate new root.249 CONNECT messages are sent across an edge when a fragment combines with another.In the case of a merge operation, CONNECT messages are sent both ways along theedge between the merging fragments in the case of an absorb operation, a CONNECTmessage is sent by the \smaller" fragment along its MWOE toward the \larger" fragment.In a bit more detail, INITIATE messages emanate outward from the designated \coreedge" to all the nodes of the fragment these INITIATE messages not only signal the nodesto look for their own MWOE (if that edge has not yet been found), but they also carryinformation about the fragment identity (the core edge and level number of the fragment).As for the TEST-ACCEPT-REJECT protocol: there's a little bookkeeping that nodes haveto do.
Every node, in order to avoid sending out redundant messages testing and re-testingedges, keeps a list of its incident edges in the order of weights. The nodes classify theseincident edges in one of three categories: Branch edges are those edges designated as part of the building spanning tree. Basic edges are those edges that the node doesn't know anything about yet | theymay yet end up in the spanning tree.
(Initially, of course, all the node's edges areclassied as basic.) Rejected edges are edges that cannot be in the spanning tree (i.e., they lead to anothernode within the same fragment).A fragment node searching for its MWOE need only send messages along basic edges.The node tries each basic edge in order, lowest weight to highest. The protocol that thenode follows is to send a TEST message with the fragment level-number and core-edge(represented by the unique weight of the core edge). The recipient of the TEST messagethen checks if its own identity is the same as the TESTer if so, it sends back a REJECTmessage. If the recipient's identity (core edge) is dierent and its level is greater than orequal to that of the TESTer, it sends back an ACCEPT message.
Finally, if the recipienthas a dierent identity from the TESTer but has a lower level number, it delays respondinguntil such time as it can send back a denite REJECT or ACCEPT.So each node nds the MWOE if it exists. All of this information is sent back to thenodes incident on the core edge via REPORT messages, who determine the MWOE for theentire fragment. A CHANGEROOT message is then sent back towards the MWOE, and theendpoint node sends a CONNECT message out over the MWOE.When two CONNECT messages cross, this is the signal that a merge operation is takingplace.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
