Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 44
Текст из файла (страница 44)
In the synchronous case,we had an easy way to measure time | by counting the number of synchronous rounds forthe synchronous version of this algorithm, we got about n. In the asynchronous case, wehave to use a real time measure similar to what we used for asynchronous shared memoryalgorithms.At this point, we pause and generalize this time measure to arbitrary IOA's.
This turnsout to be straightforward | thinking of the fairness classes as representing separate tasks,we can just associate a positive real upper bound with each class. This generalizes whatwe did for shared memory in a natural way: there, we had upper bounds for each process,and for each user. (Recall that we could model the user as a separate I/O automaton.) Inspecializing version to the reliable network model, we put an upper bound of l on each classof each process, and an upper bound of d on time for the message queue to do a step (thatis, the time to deliver the rst message in the queue).Using these denitions, we proceed with the analysis of the LeLann-Chang algorithm. Anaive approach (as in the CWI paper) gives an O(n2) bound.
This is obtained by using theprogress argument from the last lecture, adding the time bounds in along the way: in theworst case, it takesnl + nd time for the maximum UID to get from one node to the next (nltime to send it, and then nd to receive it).
Note that in this analysis, we are allowing for themaximum number of messages (n) to delay the message of interest in all the queues. Theoverall time complexity is thus O(n2 (l + d)).But it is possible to carry out a more rened analysis, thus obtaining a better upperbound. The key idea is that although the queues can grow to size at worst n and incur ndtime to deliver everything, this cannot happen everywhere. More specically, in order fora long queue to form, some messages must have been traveling faster than the worst-caseupper bound. Using this intuition, we can carry out an analysis that yields an O(n(l + d))220upper bound on time.
Informally, the idea is to associate a progress measure with each state,giving an upper bound on the time from any point when the algorithm is in that state untilthe leader is reported. Formally, we prove the following claim.Claim 1 Given a state in an execution of the algorithm, consider the distance around thering of a token (i.e., message) i from its current position to its home node i. Let k be themaximum of these distances. Then within k(l + d) + l time, a leader event occurs.Applying this claim to the initial state yields an upper bound for the algorithm of n(l +d) + l, as desired.Proof: By induction on k.Base case: k = 0, i.e., the imax token has already arrived at node imax in this case, withinl time units the leader will occur.Inductive step: Suppose the claim holds true for k ; 1, and prove it holds for k .
Supposethat k is the maximum of the indicated distances. Consider any token that is at distancegreater than k ; 1. By denition of k, no token is in distance strictly greater than k. Thismeans that the token is either in the send queue at distance k, or in the channel's queuefrom distance k to k ; 1. We now argue that this token is not \blocked" by any othertoken, i.e., that it is the only token in the combination of this send buer or this queue .To see this, notice that if another token were there also, then that other token would be atdistance strictly greater than k from its goal, a contradiction to the assumption that k is themaximum such value. So within time at most l + d, the token on which we focus gets to thenext node, i.e., to within distance k ; 1 of its goal, and then, by the inductive hypothesis,in additional time (k ; 1)(l + d) + l, a leader event occurs.
This proves the inductive step.18.1.2 The Hirshberg-Sinclair AlgorithmRecall the Hirshberg-Sinclair algorithm, which used the idea of two-directional explorationas successively doubled distances. It is straightforward to see that this algorithm still worksne in the asynchronous setting, with the same time and communication upper bounds:O(n log n).18.1.3 The Peterson AlgorithmHirshberg and Sinclair, in their original paper, conjectured that in order to get O(n log n)worst case message performance, a leader election algorithm would have to allow bidirectionalmessage passing.
Peterson, however, constructed an algorithm disproving this conjecture.More specically, the assumptions used by the Peterson algorithm are the following. The number of nodes in the ring is unknown.221Unidirectional channels.Asynchronous model.Unbounded identier set.Any node may be elected as the leader (not necessarily the maximum).The Peterson algorithm not only has O(n log n) worst case performance, but in fact theconstant factor is low it is easy to show an upper bound of 2 n log n, and Peterson useda trickier, optimized construction to get a worst case performance of 1:44 n log n.
(Theconstant has been brought even further down by other researchers.)The reason we didn't introduce this algorithm earlier in the course is that synchronydoesn't help in this case: it seems like a \naturally asynchronous" algorithm.In Peterson's algorithm, processes are designated as being either in an active mode orrelay mode all processes are initially active. We can consider the active processes as theones \doing the real work" of the algorithm | the processes still participating in the leaderelection process.
The relay processes, in contrast, just pass messages along.The Peterson algorithm is divided into (asynchronously determined) phases. In eachphase, the number of active processes is divided at least in half, so there are at most log nphases.In the rst phase of the algorithm, each process sends its UID two steps clockwise. Thus,everyone can compare its own UID to those of its two counterclockwise neighbors. When itreceives the UID's of its two counterclockwise neighbors, each process checks to see whetherit is in a conguration such that the immediate counterclockwise neighbor has the highestUID of the three, i.e., process i +1 checks if id i > id i;1 and id i > id i+1. If process i +1 ndsthat this condition is satised, it remains \active," adopting as a \temporary UID" the UIDof its immediate counterclockwise neighbor, i.e., process i. Any process for which the abovecondition does not hold becomes a \relay" for the remainder of the execution.
The job of a\relay" is only to forward messages to active processes.Subsequent phases proceed in much the same way: among active processors, only thosewhose immediate (active) counterclockwise neighbor has the highest (temporary) UID of thethree will remain active for the next phase. A process that remains active after a given phasewill adopt a new temporary UID for the subsequent phase this new UID will be that of itsimmediate active counterclockwise neighbor from the just-completed phase.
The formal codefor Peterson's algorithm is given in Figures 18.1 and 18.2.It is clear that in any given phase, there will be at least one process that nds itself in aconguration allowing it to remain active (unless only one process participates in the phase,222State of process i:mode: taking values from factive relay g, initially activestatus: taking values from funknown elected reported g, initially unknownid (j ), where j 2 f1 2 3g: type UID or nil, initially id (1) = i's UID, and id (2) = id (3) =nil .send : queue of UID's, initially containing i's UIDreceive : queue of UID'sActions of process i:get-second-uidPrecondition: mode = activereceive 6= id (2) = nilEect: id (2) head (receive )remove head of receiveadd id (2) to end of sendif id (2) = id (1) then status electediget-third-uidPrecondition: mode = activereceive 6= id (2) 6= nilid (3) = nilEect: id (3) head (receive )remove head of receiveiFigure 18.1: Peterson's algorithm for leader election: part 1223Code for process i (cont.):advance-phasePrecondition: mode = activeid (3) 6= nilid (2) > max fid (1) id (3)gEect: id (1) id (2)id (2) nilid (3) niladd id (1) to sendibecome-relayPrecondition: mode = activeid (3) 6= nilid (2) max fid (1) id (3)gEect: mode relayirelayPrecondition: mode = relayreceive 6= Eect: move head of receive to tail of sendisend message (m)Precondition: head (send ) = mEect: delete head of sendireceive message (m)Eect: add m to the tail of receiveiFigure 18.2: Peterson's algorithm for leader election: part 2224in which case the lone remaining process is declared the winner).
Moreover, at most half thepreviously active processes can survive a given phase, since for every process that remainsactive, there is an immediate counterclockwise active neighbor that must go into its relaystate. Thus, as stated above, the number of active processes is at least halved in each phase,until only one active process remains.Communication and Time Analysis. The total number of phases in Peterson's algorithm is at most blog nc, and during each phase each process in the ring sends and receivesexactly two messages. (This applies to both active and relay processes.) Thus, there areat most 2n blog nc messages sent in the entire algorithm.
(Note that this a much betterconstant factor than in the Hirshberg-Sinclair algorithm.)As for time performance, one might rst estimate that the algorithm should take O(n log n)time, since there are log n phases, and each phase could involve a chain of message deliveries (passing through relays) of total length O(n).
As it turns out, however, the algorithmterminates in O(n) time. We give a brief sketch of the time analysis. Again, we may neglect \pileups", which seem not to matter for the same reason as in the analysis of LeLann.This allows us to simplify the analysis by assuming that every node gets a chance to senda message in between every two receives. For simplicity, we also assume that local processing time is negligible compared to the message-transmission time d, so we just consider themessage-transmission time.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
