Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 48
Текст из файла (страница 48)
At any point in the algorithm, each of a collection of fragments may independentlyand concurrently nd its own minimum-weight outgoing edge (MWOE), knowing that allsuch edges found must be included in the unique MST. (Note that if the edge weights werenot distinct, the fragments couldn't carry out this choice independently, since it would bepossible for them to form a cycle.)This was the basis of the synchronous algorithm. It worked in synchronous levels, wherein each level, all fragments found their MWOE's and combined using these, to form at mosthalf as many fragments.If we try to run the given synchronous algorithm in an asynchronous network, we seesome problems.Diculty 1: In the synchronous case, when a node queries a neighbor to see if it is in thesame fragment, it knows that the neighbor node is up-to-date, at the same level.
Therefore,if the neighbor has a distinct fragment id, then this fact implies that the neighbor is not inthe same fragment. But in the asynchronous setting, it could be the case that the neighborhas not yet heard that it is in the same fragment.Diculty 2: The synchronous algorithm achieves a message cost of O(n log n + E ), basedon a balanced construction of the fragments. Asynchronously, there is danger of constructing the fragments in an unbalanced way, leading to many more messages. The number ofmessages sent by a fragment to nd its MWOE will be proportional to the number of nodesin the fragment.
Under certain circumstances, one might imagine the algorithm proceedingby having one large fragment that picks up a single node at a time, each time requiring (f )messages, where f is the number of nodes in the fragment (see Figure 19.2) . In such asituation, the algorithm would require (n2) messages to be sent overall.242Figure 19.2: How do we avoid a big fragment growing by one node at a time?19.2.4 The Gallager-Humblet-Spira Algorithm: OutlineThese diculties lead us to re-think the algorithm to modify it for use in an asynchronousnetwork.
Luckily, the basic ideas are the same. The algorithm we shall see below is byGallager-Humblet-Spira. They focus on keeping the number of messages as small as possible,and manage to achieve the same O((n log n) + E ) message bound as in the synchronousalgorithm.Before we continue, let us make a few preliminary remarks. First, consider the questionwhether this is the minimum bound possible. Note that, at least for some graphs (e.g., rings),the n log n term is necessary | it comes from the lower bound on the number of messagesfor leader election that we saw in Burns' theorem.
What about the E term? This seemsessential. In a work by Awerbuch-Goldreich-Peleg-Vainish, they show that the number ofbits of communication must be at least (E log n). If we assume that each message containsonly a constant number of id's, then this means that the number of messages is (E ). Ifthe messages are allowed to be of arbitrary size, however, then it can be shown that O(n)messages suce.Another thing we would like to say about the Gallager-Humblet-Spira algorithm is thatnot only is it interesting, but it is also extremely clever: as presented in their paper, it isabout two pages of tight, modular code, and there is a good reason for just about every linein the algorithm.
In fact, only one or two tiny optimizations have been advanced over theoriginal algorithm. The algorithm has been proven correct via some rather dicult formalproofs (see WelchLL88]) and it has been referenced and elaborated upon quite often insubsequent research.
It has become a sort of test case for algorithm proof techniques.As in the synchronous algorithm we saw earlier, the central idea of the Gallager-HumbletSpira algorithm is that nodes form themselves into collections | i.e., fragments | of increasing size. (Initially, all nodes are considered to be in singleton fragments.) Each fragmentis itself connected by edges that form a MST for the nodes in the fragment. Within anyfragment, nodes cooperate in a distributed algorithm to nd the MWOE for the entire fragment (that is, the minimum weight edge that leads to a node outside the fragment). The243strategy for accomplishing this involves broadcasting over the edges of the fragment, askingeach node separately for its own MWOE leading outside the fragment.
Once all these edgeshave been found, the minimal edge among them will be selected as an edge to include in the(eventual) MST.Once an MWOE for a fragment is found, a message may be sent out over that edge tothe fragment on the other side. The two fragments may then combine into a new, largerfragment. The new fragment then nds its own MWOE, and the entire process is repeateduntil all the nodes in the graph have combined themselves into one giant fragment (whoseedges are the nal MST).This is not the whole story, of course there are still some problems to overcome. First,how does a node know which of its edges lead outside its current fragment? A node infragment F can communicate over an outgoing edge, but the node at the other end needssome way of telling whether it too is in F . We will therefore need some way of namingfragments so that two nodes can determine whether they are in the same fragment.
But theissue is still more complicated: it may be, for example, that the other node (at the end of theapparently outgoing edge) is in F but hasn't learned this fact yet, because of communicationdelays. Thus, some sort of overall synchronization process is needed|some sort of strategythat ensures that nodes won't search for outgoing edges until all nodes in the fragment havebeen informed of their current fragment.And there is also the second problem, discussed above, of the unbalanced merging behavior causing excessive message cost. This second problem should suggest a \balanced-treealgorithm" solution: that is, the diculty derives from the merging of data structures thatare very unequal in size. The strategy that we will use, therefore, is to merge fragments ofroughly equal size.
Intuitively, if we can keep merging fragments of nearly equal size, we cankeep the number of total messages to O(n log n).The trick we will use to keep the fragments at similar sizes is to associate a level numberwith each fragment. We will ensure that if level (F ) = l for a given fragment F , then thenumber of nodes in F is greater than or equal to 2l.
Initially, all fragments are just singletonnodes at level 0. When two fragments at level l are merged together, the result is a newfragment at level l + 1. (This preserves the condition for level numbers: if two fragments ofsize at least 2l are merged, the result is a new fragment of size at least 2l+1.)So far, this may look similar to the way the level numbers were used in the synchronousalgorithm, but it will actually be somewhat dierent. E.g., in the synchronous case, we couldmerge some arbitrary number of level l fragments to get a new level l + 1 fragment.The level numbers, as it turns out, will not only be useful in keeping things balanced,but they will also provide some identier-like information helping to tell nodes whether they244are in the same fragment.19.2.5 In More DetailThere are two ways of combining fragments.1.
Merging. This combining rule is applied when we have two fragments F and F 0 withthe same level and the same minimum-weight outgoing edge:level (F ) = level (F 0) = lMWOE(F ) = MWOE(F 0)The result of a merge is a new fragment at a level of l + 1.2. Absorbing. There is another case to consider. It might be that some nodes are forminginto huge fragments via merging, but isolated nodes (or small fragments) are laggingbehind at a low level. In this case, the small fragments may be absorbed into thelarger ones without determining the MWOE of the large fragment.
Specically, therule for absorbing is that if two fragments F and F 0 satisfy level (F ) < level (F 0), andthe MWOE(F ) leads to F 0, then F can be absorbed into F 0 by combining them alongMWOE(F ). The larger fragment formed is still at the level of F 0. In a sense, we don'twant to think of this as a \new" fragment, but rather as an augmented version of F 0.These two combining strategies are illustrated (in a rough way) by Figure 19.3. It isworth stressing the fact that level(F ) < level(F 0) does not imply that fragment F is smallerthan F 0 in fact, it could be larger. (Thus, the illustration of F as a \small" fragment inFigure 19.3 is meant only to suggest the typical case.)Level numbers also serve, as mentioned above, as identifying information for fragments.For fragments of level 1 or greater, however, the specic fragment identier is the core edgeof the fragment.
The core edge is the edge along which the merge operation resulting in thecurrent fragment level took place. (Since level numbers for fragments are only incrementedby merge operations, any fragment of level 1 or greater must have had its level numberincremented by some previous merge along an edge.) The core edge also serves as the sitewhere the processing for the fragment originates and where information from the nodes ofthe fragment is collected.To summarize the way in which core edges are identied for fragments: For a merge operation, core is the common MWOE of the two combining fragments. For an absorb operation, core is the core edge of the fragment with the larger levelnumber.245' $' $& %& %'& $%F-F0F -F0Figure 19.3: Two fragments combine by merging a fragment absorbs itself into anotherNote that identifying a fragment by its core edge depends on the assumption that alledges have unique identiers.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
