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

Clearly, no one would even think of using this algorithm! Itserves here just as a counterexample algorithm.Each process spawns a message which moves around the ring, carrying the UIDof the original process. Identiers that originate at dierent processes are transmitted at dierent rates. In particular, UID v travel at the rate of 1 messagetransmission every 2v clock pulses.

Any slow identier that is overtaken by afaster identier is deleted (since it has a larger identier). Also, identier v arriving at process w will be deleted if w < v. If an identier gets back to theoriginator, the originator is elected.This strategy guarantees that the process with the smallest identier gets all the way aroundbefore the next smaller gets half-way, etc., and therefore (up to the time of election) woulduse more messages than all the others combined.

Therefore total number of messages (upto the time of election) is less than 2n. The time complexity, as mentioned above, is n 2M .Also, note that by the time the minimum gets all the way around, all other transmissionshave died out, and thus 2n is an upper bound on the number of messages that are ever sentby the algorithm (even after the \leader" message is output).We remark that algorithms 1, 2 and 4 can also be used with the processors waking upat dierent times. The rst two algorithms require no modication, but algorithm 4 needssome work in order to maintain the desired complexities.2.1.3 Lower Bound on Comparison-Based ProtocolsWe have seen several algorithms for leader election on a ring.

Algorithm 2 was comparisonbased, and had the complexity of O(n log n) messages and O(n) time. Algorithms 3 and4 were non-comparison-based, and had O(n) messages, with huge running time. To gainfurther understanding of the problem, we now show a lower bound of !(n log n) messages forcomparison-based algorithms Frederickson-Lynch, Attiya-Snir-Warmuth]. This lower boundholds even if we assume that n is known to the processors.28The result is based on the diculty of breaking symmetry.

Recall the impossibility prooffrom last time, where we showed that because of the symmetry, it is impossible to elect aleader without identiers. The main idea in the argument that we shall use below is thatsymmetry is possible with identiers also | now it is possible to break it, but it must requiremuch communication.Before we state the main results, we need some denitions.Denition 1 We call a distributed protocol comparison-based algorithm if the nodes areidentical except for UID's, and the only way that UID's can be manipulated is to copy them,and to compare them for f< > =g (the results of the comparisons are used to make choiceswithin the state machine).

UIDs can be sent in messages, perhaps combined with otherinformation.Intuitively, the decisions made by the state machines depend only on the relative ranksof the UIDs, rather than their value.The following concept will be central in the proof.Denition 2 Let X = (x1 x2 : : : xr) and Y = (y1 y2 : : : yr ), be two strings of UIDs.

Wesay that X is order equivalent to Y if, for all 1 i j r, we have xi xj if and only ifyi yj .Notice that two strings of UIDs are order equivalent if and only if the correspondingstrings of relative ranks of their UIDs are identical.The following denitions are technical.Denition 3 A computation round is called an active round if at least one (non-null) message is sent in it.Denition 4 The k-neighborhood of process p in ring of size n, where k < bn=2c, is denedto consist of the 2k + 1 processes at distance at most k from p.The following concept is a key concept in the argument.Denition 5 We say that two states s and t correspond with respect to strings X =(x1 x2 : : : xr ) and Y = (y1 y2 : : : yr), if all of the UID's in s are chosen from X , andt is identical to s except for substituting each occurrence of any xi in s, by yi in t, for all1 i r.Corresponding messages are dened analogously.We can now start proving our lower bound.Lemma 1 Let p and q be two distinct processes executing a comparison-based algorithm.Suppose that p and q have order-equivalent k -neighborhoods.

Then at any point after at mostk active rounds, p and q are in corresponding states, with respect to their k-neighborhoods.29p1pq1p2q2qFigure 2.2: scenario in the proof of Lemma 1Proof: By induction on the number r of rounds in the computation. Notice that possiblyr > k. For each r, we prove the lemma for all k.Basis : r = 0. By Denition 1, the initial states of p and q are identical except fortheir UIDs, and hence they are in corresponding initial states, with respect to their 0neighborhoods (consisting of nothing but their own UID's).Inductive step : Assume that the lemma holds for all r0 < r.

Let p1 and p2 be therespective counterclockwise and clockwise neighbors of p, and similarly q1 and q2 for q.We proceed by case analysis.1. Suppose that neither p nor q receives a message from either neighbor at round r. Then,by the induction hypothesis (on r, using same k), p and q are in corresponding statesbefore r, and since they have no new input, they make corresponding transitions andend up in corresponding states after r.2.

Suppose now that at round r, p receives a message from p1 but no message from p2.Then round r is active. By induction, p1 and q1 are in corresponding states with respectto their (k ; 1)-neighborhoods, just before round r. Hence, q1 also sends a messageto q in round r, and it corresponds to the message sent by p1, (with respect to the(k ; 1)-neighborhoods of p1 and q1, and therefore with respect to the k-neighborhoodsof p and q).

Similarly, p2 and q2 are in corresponding states with respect to theirk ; 1-neighborhoods, just before round r, and therefore q2 does not send a messageto q at round r. Also, by induction, p and q are in corresponding states with respectto their k ; 1-neighborhoods, and hence with respect to their k-neighborhoods, justbefore round r. So after they receive the corresponding messages, they remain incorresponding states with respect to their k-neighborhoods.3. Finally, suppose p receives a message from p2.

We use the same argument as in theprevious case to argue that lemma holds in the two subcases (either p1 send a messageat round r or not).Lemma 1 tells us that many active rounds are necessary to break symmetry, if thereare large order-equivalent neighborhoods. We now dene particular rings with the specialproperty that they have many order-equivalent neighborhoods of various sizes.30position=7, ID=111 (7)position=0, ID=000 (0)position=6, ID=011 (3)position=1, ID=100 (4)position=2, ID=010 (2)position=5, ID=101 (5)position=3, ID=110 (6)position=4, ID=001 (1)Figure 2.3: Bit-reversal assignment has 1/2-symmetryDenition 6 Let c 1 bepa constant, and let R be a ring of size n. R is said to havec-symmetry if for every `, n ` n, and for every segment S of R of length `, there areat least cn` segments in R that are order-equivalent to S (counting S itself).Remark : the square root is a technicality.Example : For n a power of 2, we shall show that the bit-reversal ring of size n has 1=2symmetry.

Specically, suppose n = 2a. We assign to each process i the integer in the range0 n ; 1] whose a-bit binary representation is the reverse of the a-bit binary representationof i.For instance, for n = 8, we have a = 3, and the assignment is in Figure 2.3.The bit-reversal ring is highly symmetric, as we now claim.Claim 2 The bit-reversal ring is 1=2-symmetric.Proof: Left as an exercise.We remark that for the bit-reversal ring, there is even no need for the square root caveat.For other values of n, non-powers of 2, there is a more complicated construction that canyield c-symmetry for some smaller constant c.

The construction is complicated since simplyadding a few extra processors could break the symmetry.Now, suppose we have a ring R of size n with c-symmetry. The following lemma statesthat this implies many active rounds.Lemma3 Suppose that algorithm A elects a leader in a c-symmetric ring, and let k be suchpthat n 2k + 1 n and 2kcn+1 2. Then A has more than k active rounds.Proof: By contradiction: suppose A elects a leader, say p, in at most k active rounds.