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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 46)

This means that at most n4 processes in join (L M )\know about" the join, and these are contiguous and adjacent to the boundary as shown inFigure 18.10. These processes extend at most halfway into either segment. Let us call thisexecution LM . Similarly for LN , etc.Mp1R1NLFigure 18.11: ring (join (L M N )): case 1In ring R1 of Figure 18.11, consider an execution in which L, M , and N occur rst,quiescing in three pieces separately.

Then quiesce around boundaries as in LM , LN , andNL. Since the processes that know about each join extend at most half way into eithersegment, these messages will be non-interfering. Similarly for R2.Each of R1 and R2 elects a leader, say p1 and p2. We can assume without loss of generalitythat p1 is between the midpoint of L and the midpoint of M as in Figure 18.11. We considercases based on the position of p2 in R2 (Figure 18.12) to get a contradiction.If p2 is between the midpoint of L and the midpoint of N as in Figure 18.12, then letR3 be assembled by joining just M and N .

Consider an execution of R3 in which the two231Np2R2MLFigure 18.12: ring (join (L N M ))segments are rst run to quiescence using M and N , and then quiescence occurs aroundthe boundaries, as in MN and NM .R3MNp3Figure 18.13: ring (join (M N )): leader elected in the lower halfNp2R2p3MLFigure 18.14: ring (join (L N M ))By the problem denition, a leader must be elected in R3, say p3 .

First suppose it isin lower half as in Figure 18.13. Then it also occurs in R2 and gets elected there too as in232Figure 18.14. There are two leaders in this case which is a contradiction. If it is in the upperhalf of R3, then we arrive at a similar contradiction in R1.If p2 is between the midpoint of L and the midpoint of M , then we arrive at a similarcontradiction based on R3, again.R4LNFigure 18.15: ring (join (L N ))If p2 is between the midpoint of M and the midpoint of N , then we arrive at a similarcontradiction based on R4, a ring containing LN as in Figure 18.15.The lemma follows from the claim.Lemma 3 essentially proves Theorem 2: let n be a power of 2. Pick a line L of lengthn with COMM (L) 1 + n4 log n, and paste it into a circle using the ring operator.

Let theprocesses in L behave exactly as they would if they were not connected, in the executionthat sends the large number of messages, and delay all messages across the pasted boundaryuntil all the large number of messages have been sent. This gives us the desired bound.Note the crucial part played by the asynchrony in this argument.18.2 Problems in General Asynchronous NetworksSo far, we have revisited several synchronous ring leader election algorithms from the beginning of the course, and have seen that they extend directly to the asynchronous setting. Nowwe will reexamine the algorithms from more general synchronous networks.

In the sequel weshall assume that the underlying communication network is modeled by a general undirectedgraph.18.2.1 Network Leader ElectionThe synchronous algorithm we saw earlier for leader election in a general graph does notextend directly to the asynchronous model. In the synchronous algorithm, every node main233tains a record of the maximum UID it has seen so far (initially its own).

At each round, thenode propagates this maximum on all its incident edges. The algorithm terminates after anumber of rounds equal to the diameter if the process has its own ID as its known maximum,then it announces itself as the leader.In the asynchronous setting we don't have rounds, and we don't have any informationabout time that would allow us to wait for enough time to hear from everyone, and so theabove idea doesn't extend. We could still follow the basic strategy of propagating maximumUID's asynchronously: whenever a process gets a new maximum, it propagates it sometimelater. The problem is now that we don't know when to stop. To overcome this problem, weshall use other techniques.18.2.2 Breadth-rst Search and Shortest PathsReconsider the shortest paths algorithms. (Recall that breadth-rst search is a special caseof shortest paths, when all edges have weights 1.) In these algorithms, we assume that weare given an initiator node i0, and we want that each node (eventually) outputs a pointer toa parent in a shortest-paths (or breadth-rst) tree.

We can also output the distance on theshortest path.The algorithms we have presented earlier used the synchrony very heavily. E.g., forbreadth-rst search, we marked nodes in layers, one layer for each synchronous round. Thiswas very ecient: O(E ) total messages, and time proportional to the diameter.We cannot run that algorithm directly in an asynchronous network, since dierent branchesof the tree can grow more quickly than others.

More specically, this means that a node canget some information about one path rst, then later nd out about a shorter path. Thus,we need to be able to adjust estimates downward when new information arrives. Recall thatthe synchronous shortest-paths algorithm we saw earlier already did this kind of adjustment.(We called it a \relaxation step".)This adjustment idea is used in a famous shortest-paths (and BFS) algorithm that imitates the Bellman-Ford algorithm from sequential complexity theory.

In fact, this algorithmwas the routing algorithm used in the ARPANET between 1969 and 1980. Note that thiswill not be a terminating algorithm | the nodes will not know when they are done. We givethe specication of this algorithm in precondition/eects style in Figure 18.16.234State variables:best-dist, for i0 this is initially 0, for others 1parent, initially undenednew-send, for i0 initially neighbors (i0), for others initially (says whom they should send a newly-discovered distance to).Signature: We assume that the weights are known a priori, so no inputs are needed fromthe outside world.

We need send and receive actions, as usual the only message is adistance value (nonnegative real). There are no outputs (since not known when thisterminates).Actions:send i j (m)Precondition: j 2 new-sendm = best-distEect: new-send new-send ; fj greceive j i(m)Eect: if m + weight (j i) < best-dist thenbest-dist m + weight (j i)new-send neighbors (i) ; fj gparent jFigure 18.16: Bellman-Ford algorithm for shortest paths235Analysis.

If the algorithm were executed in synchronous rounds, then the time would beO(n), where n is the total number of nodes, and the number of messages would be O(njE j).This does not seem too bad. But in asynchronous execution the time bound can be muchworse: in fact, we show below that the time and message complexity are exponential in n.Claim 5 The algorithm sends (2n ) messages in the worst case.Proof: Consider the example illustrated in Figure 18.17.2^ki002^(k−1)i102i201ik0i(k+1)i(k+2)Figure 18.17: Bad scenario for the Bellman-Ford AlgorithmThe possible estimates that ik+1 can have for its best-dist are 0 1 2 3 : : : 2k+1 ; 1.

Moreover, we claim that it is possible for ik+1 to acquire all of these estimates, in order fromthe largest to the smallest. To see how, consider the following scenario. Suppose that themessages on the upper paths all propagate rst, giving ik+1 the estimate 2k+1 ; 1. Next, the\alternative" message from ik arrives, giving ik+1 the adjusted estimate of 2k+1 ; 2. Next,the \alternative" message from ik;1 to ik arrives at ik , cause ik to reduce its estimate by 2.It then propagates this revision on both paths.

Again, suppose the message on the upperpath arrives rst, etc.Since ik+1 gets 2k+1 distinct estimates, it is possible, if ik+1 takes steps fast enough, forik+1 to actually put all these values in the outgoing channel to ik+2. This yields exponentiallymany messages (actually, (2n=2)). Moreover, the time complexity is similarly bad, becausethese messages all get delivered sequentially to ik+2.We now consider upper bounds on the Bellman-Ford algorithm. First, we claim thatthe number of messages is O((n + 1)n e) at most. This is because each node only sendsnew messages out when it gets a new estimate. Now, each estimate is the total weight ofa simple path to that node from i0, and the bound follows from the fact that there are atmost (n +1)n such paths. (This may be a loose estimate.) Now consider any particular edge.It only gets messages when one of its endpoints gets a new estimate, leading to a total of2(n + 1)n messages on that edge.2366.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchNovember 17, 1992Lecture 1919.1 Asynchronous Broadcast-ConvergecastIn an earlier lecture, we described a synchronous discipline for broadcasting and convergecasting (sometimes called broadcast-with-echo), using a breadth-rst spanning tree.

Характеристики

Список файлов книги