分布式算法课件

1、1,Leader Election in Rings,沈卓炜 九龙湖校区计算机楼347房间 Tel:520909192011年3月,2,Ring Networks,In an oriented ring, processors have a consistent notion of left and right For example, if messages are always forwarded on channel 1, they will cycle clockwise around the ring,3,Why Study Rings?,simple st

2、arting point, easy to analyze abstraction of a token ring lower bounds and impossibility results for ring topology also apply to arbitrary topologies,4,Leader Election Definition,Each processor has a set of elected (won) and not-elected (lost) states. Once an elected state is entered, processor is a

3、lways in an elected state (and similarly for not-elected): i.e., irreversible decision In every admissible execution: every processor eventually enters either an elected or a not-elected state exactly one processor (the leader) enters an elected state,5,Uses of Leader Election,A leader can be used t

4、o coordinate activities of the system: find a spanning tree using the leader as the root reconstruct a lost token in a token-ring network We will study leader election in rings.,6,Anonymous Rings,How to model situation when processors do not have unique identifiers? First attempt: require each proce

5、ssor to have the same state machine Subtle point: does algorithm rely on knowing the ring size (number of processors)?,7,Uniform (Anonymous) Algorithms,A uniform algorithm does not use the ring size (same algorithm for each size ring) Formally, every processor in every size ring is modeled with the

6、same state machine A non-uniform algorithm uses the ring size (different algorithm for each size ring) Formally, for each value of n, every processor in a ring of size n is modeled with the same state machine An . Note the lack of unique ids.,8,Leader Election in Anonymous Rings,Theorem: There is no

7、 leader election algorithm for anonymous rings, even if algorithm knows the ring size (non-uniform) synchronous model Proof Sketch: Every processor begins in same state with same outgoing msgs (since anonymous) Every processor receives same msgs, does same state transition, and sends same msgs in ro

8、und 1 Ditto for rounds 2, 3, Eventually some processor is supposed to enter an elected state. But then they all would.,9,Leader Election in Anonymous Rings,Proof sketch shows that either safety (never elect more than one leader) or liveness (eventually elect at least one leader) is violated. Since t

9、he theorem was proved for non-uniform and synchronous rings, the same result holds for weaker (less well-behaved) models: uniform asynchronous,10,Rings with Identifiers,Assume each processor has a unique id. Dont confuse indices and ids: indices are 0 to n - 1; used only for analysis, not available

10、to the processors ids are arbitrary nonnegative integers; are available to the processors through local variable id.,11,Start with the smallest id and list ids in clockwise order. Example: 3, 37, 19, 4, 25,Specifying a Ring,id = 3,id = 25,id = 4,id = 19,id = 37,12,Uniform (Non-anonymous) Algorithms,

11、Uniform algorithm: there is one state machine for every id, no matter what size ring Non-uniform algorithm: there is one state machine for every id and every different ring size These definitions are tailored for leader election in a ring.,13,Overview of LE in Rings with Ids,There exist algorithms w

12、hen nodes have unique ids. We will evaluate them according to their message complexity. asynchronous ring: (n log n) messages synchronous ring: (n) messages under certain conditions otherwise (n log n) messages All bounds are asymptotically tight.,14,O(n2) Messages LE Algorithm,send value of own id

13、to the left when receive an id j (from the right): if j id then forward j to the left (this processor has lost) if j = id then elect self (this processor has won) if j id then do nothing,15,Analysis of O(n2) Algorithm,Correctness: Elects processor with largest id. msg containing largest id passes th

14、rough every processor Time: O(n) Message complexity: Depends how the ids are arranged. largest id travels all around the ring (n msgs) 2nd largest id travels until reaching largest 3rd largest id travels until reaching largest or second largest etc.,16,Analysis of O(n2) Algorithm,Worst way to arrang

15、e the ids is in decreasing order: 2nd largest causes n - 1 messages 3rd largest causes n - 2 messages etc. Total number of messages is n + (n-1) + (n-2) + + 1 = (n2).,17,Can We Use Fewer Messages?,The O(n2) algorithm is simple and works in both synchronous and asynchronous model. But can we solve th

16、e problem with fewer messages? Idea: Try to have msgs containing smaller ids travel smaller distance in the ring,18,O(n log n) Leader Election Algorithm,Each proc. tries to probe successively larger neighborhoods in both directions size of neighborhood doubles in each phase If probe reaches a node w

17、ith a larger id, the probe stops If probe reaches end of its neighborhood, then a reply is sent back to initiator If initiator gets back replies from both directions, then go to next phase If proc. receives a probe with its own id, it elects itself,19,O(n log n) Leader Election Algorithm,20,Analysis

18、 of O(n log n) Leader Election Algorithm,Correctness: Similar to O(n2) algorithm. Message Complexity: Each msg belongs to a particular phase and is initiated by a particular proc. Probe distance in phase i is 2i Number of msgs initiated by a proc. in phase i is at most 4*2i (probes and replies in bo

19、th directions),21,Analysis of O(n log n) Leader Election Algorithm,How many procs. initiate probes in phase i ? For i = 0, every proc. does For i 0, every proc. that is a winner in phase i - 1 does winner means has largest id in its 2i-1 neighborhood,22,Analysis of O(n log n) Leader Election Algorit

20、hm,Maximum number of phase i - 1 winners occurs when they are packed as densely as possible: total number of phase i - 1 winners is at most n/(2i-1 + 1),23,Analysis of O(n log n) Leader Election Algorithm,How many phases are there? At each phase the number of (phase) winners is cut in half (at least

21、) So after at most log2 n phases, only one winner is left.,24,Analysis of O(n log n) Leader Election Algorithm,Total number of messages is sum, over all phases, of number of winners at that phase times number of messages originated by that winner:,phase 0 msgs,msgs for phases 1 to log n,termination

22、msgs,25,Can We Do Better?,The O(n log n) algorithm is more complicated than the O(n2) algorithm but uses fewer messages in worst case. Works in both synchronous and asynchronous case. Can we reduce the number of messages even more? Not in the asynchronous model,26,Asynchronous Lower Bound on Message

23、s,(n log n) lower bound for any leader election algorithm A that (1) works in an asynchronous ring (2) is uniform (doesnt use ring size) (3) elects maximum id (4) guarantees everyone learns id of winner,necessary for result to hold,necessary for this proof to work,no loss of generality,no loss of ge

24、nerality,27,Statement of Key Result,Theorem (3.5): For every n that is a power of 2 and every set of n ids, there is a ring using those ids on which any asynchronous leader election has a schedule in which at least M(n) messages are sent, where M(2) = 1 and M(n) = 2M(n/2) + (n/2 - 1)/2, n 2. Why doe

25、s this give (n log n) result? because M(n) = (n log n),28,Discussion of Statement,power of 2: can be adapted for other case schedule: the sequence of events (and events only) extracted from an execution, i.e., discard the configurations configuration gives away number of processors but we will want

26、to use the same sequence of events in different size rings,29,Idea of Asynchronous Lower Bound,The number of messages, M(n), is described by a recurrence: M(n) = 2 M(n/2) + (n/2 - 1)/2 Prove the bound by induction Double the ring size at each step so induction is on the exponent of 2 Show how to con

27、struct an execution on a larger ring by starting with two executions on smaller rings (2*M(n/2) and then causing about n/4 extra messages to be sent,30,Open Schedules,To make the induction go through, the executions must have schedules that are open. Definition of open schedule: There is an edge ove

28、r which no message is delivered. An edge over which no message is delivered is called an open edge.,31,Suppose n = 2. Suppose x y. Then p0 wins and p1 must learn that the leader id is x. So p0 must send a message to p1. Truncate immediately after the message is sent (before it is delivered) to get d

29、esired open schedule.,Proof of Base Case,p0,p1,p1,x,y,32,Proof of Inductive Step,Suppose n 4. Split S (set of ids) into two halves, S1 and S2. By inductive hypothesis, there are two rings, R1 and R2:,33,Apply Inductive Hypothesis,R1 has an open schedule 1 in which at least M(n/2) messages are sent a

30、nd e1 = (p1,q1) is an open edge.,R2 has an open schedule 2 in which at least M(n/2) messages are sent and e2 = (p2,q2) is an open edge.,34,Paste Together Two Rings,Paste R1 and R2 together over their open edges to make big ring R. Next, build an execution of R with M(n) messages,35,Paste Together Tw

31、o Executions,Execute 1: procs. on left cannot tell difference between being in R1 and being in R. So they behave the same and send M(n/2) msgs in R. Execute 2: procs. on right cannot tell difference between being in R2 and being in R. So they behave the same and send M(n/2) msgs in R.,depends on uni

32、form assumption,36,Generating Additional Messages,Now we have 2*M(n/2) msgs. How to get the extra (n/2 - 1)/2 msgs? Case 1: Without unblocking (delivering a msg on) ep or eq, there is an extension of 1 2 on R in which (n/2 - 1)/2 more msgs are sent. Then this is the desired open schedule.,37,Generat

33、ing Additional Messages,Case 2: Without unblocking (delivering a msg on) ep or eq, every extension of 1 2 on R leads to quiescence: no proc. will send another msg. unless it receives one no msgs are in transit except on ep and eq Let 3 be any extension of 1 2 that leads to quiescence.,38,Getting n/2

34、 More Messages,Let 4 be an extension of 1 2 3 that leads to termination. Claim: At least n/2 messages are sent in 4. Why? Each of the n/2 procs. in the half of R not containing the leader must receive a msg to learn the leaders id. Until 4 there has been no communication between the two halves of R

35、(remember the open edges),depends on assumption that all learn leaders id,39,Getting an Open Schedule,Remember we want to use this ring R and this execution as building blocks for the next larger power of 2, in which we will paste together two open executions So we have to find an open execution (wi

36、th at least one edge over which no msg is delivered). 1 2 3 4 might not be open A little more work is needed,40,Getting an Open Schedule,As msgs in ep and eq are delivered in 4, procs. wake up from quiescent state and send more msgs. Sets of awakened procs.(P and Q) expand outward around ep and eq :

37、,41,Getting an Open Schedule,Let 4 be the prefix of 4 when n/2 - 1 msgs have been sent P and Q cannot meet in 4, since less than n/2 msgs are sent in 4 W.l.o.g., suppose the majority of these msgs are sent by procs in P (at least (n/2 - 1)/2 msgs) Let 4 be the subsequence of 4 consisting of just the

38、 events involving procs. in P,42,Getting an Open Schedule,When executing 1234, processors in P behave the same as when executing 1234. Why? The only difference between 4 and 4 is that 4 is missing the events by procs. in Q. But since there is no communication in 4 between procs. in P and procs. in Q

39、, procs. in P cannot tell the difference.,depends on asynchrony assumption,43,Wrap Up,Consider schedule 1234 . During 1, M(n/2) msgs are sent, none delivered over ep or eq During 2, M(n/2) msgs are sent, none delivered over ep or eq During 3, all msgs are delivered except those over ep or eq; possib

40、ly some more msgs are sent During 4, (n/2 - 1)/2 msgs are sent, none delivered over eq (why?) This is our desired schedule for the induction!,44,Leader Election in SynchronousRings,Here is a simple algorithm. Group rounds into phases, each phase containing n rounds In phase i, the processor with id

41、i, if there is one, sends a message around the ring and is elected.,45,Example of Simple Synchronous Algorithm,n = 4, the smallest id is 7. In phases 0 through 6 (corresponding to rounds 1 through 28), no message is ever sent. At beginning of phase 7 (round 29), processor with id 7 sends message whi

42、ch is forwarded around the ring.,Relies on synchrony and knowing n,46,Analysis of Simple Algorithm,Correctness: Easy to see. Message complexity: O(n), which is optimal Time complexity: O(n*m), where m is the smallest id in the ring.,47,Another Synchronous Algorithm,Works in a slightly weaker model t

43、han the previous synchronous algorithm: processors might not all start at same round; a processor either wakes up spontaneously or when it first gets a message uniform (does not rely on knowing n),48,Another Synchronous Algorithm,A processor that wakes up spontaneously is active; sends its id in a f

44、ast message (one edge per round) A processor that wakes up when receiving a msg is relay; never in the competition A fast message carrying id m becomes slow if it reaches an active processor; starts traveling at one edge per 2m rounds A processor only forwards a msg whose id is smaller than any id i

45、t has previously sent If a proc. gets its own id back, elects self,49,Analysis of Synchronous Algorithm,Correctness: convince yourself that the active processor with smallest id is elected. Message complexity: Winners msg is the fastest. While it traverses the ring, other msgs are slower, so they ar

46、e overtaken and stopped before too many messages are sent.,50,Message Complexity,Divide msgs into three kinds: fast msgs slow msgs sent while the leaders msg is fast slow msgs sent while the leaders msg is slow Next, count the number of each type of msg.,51,Show that no processor forwards more than

47、one fast msg: Suppose pi forwards pj s fast msg and pk s fast msg. When pk s fast msg arrives at pj : either pj has already sent its fast msg, so pk s msg becomes slow, or pj has not already sent its fast msg, so it never will Number of type 1 msgs is n.,Number of Type 1 Messages,pk,pj,pi,52,Number

48、of Type 2 Messages,(slow sent while leaders msg is fast) Leaders msg is fast for at most n rounds by then it would have returned to leader Slow msg i is forwarded n/2i times in n rounds Max. number of msgs is when ids are small as possible (0 to n-1 and leader is 0) Number of type 2 msgs is at most

49、n/2i n,i=1,n-1,53,Number of Type 3 Messages,(slow msgs sent while leaders is slow) Maximum number of rounds during which leaders msg is slow is n*2L (L is leaders id). No msgs are sent once leaders msg has returned to leader Slow msg i is forwarded n*2L/2i times during n*2L rounds. Worst case is whe

50、n ids are L to L + n-1 Number of type 3 msgs is at most n*2L/2i 2n,i=L,L+n-1,54,Total Number of Messages,We showed number of type 1 msgs is at most n number of type 2 msgs is at most n number of type 3 msgs is at most 2n Thus total number of msgs is at most 4n = O(n).,55,Time Complexity of Synchrono

51、us Algorithm,Running time is O(n 2x), where x is smallest id. Even worse than previous algorithm, which was O(n x) Both algorithms have two potentially undesirable properties: rely on numeric values of ids to count number of rounds bears no relationship to n, but depends on minimum id Next result sh

52、ows that to obtain linear msg complexity, an algorithm must rely on numeric values of the ids.,56,Comparison-Based LE Algorithms,We will show that if nodes cannot rely on the numeric values of the ids, then any synchronous LE algorithm has message complexity (n log n). How do we formalize not relyin

53、g on numeric values of ids? Need a definition of comparison-based, similar to that for sorting algs.,57,Definition of Comparison-Based,First note that in the synchronous model, the behavior of an LE algorithm is totally determined by the distribution of the ids. Denote execution on ring R by exec(R)

54、. An LE algorithm is comparison-based if, in any two order-equivalent rings R1 and R2, matching processors pi in R1 and pj in R2 have similar behaviors in exec(R1) and exec(R2).,58,Definition of Order-Equivalent,Rings R1 = (x1,x2,xn) and R2 = (y1,y2,yn) are order-equivalent if xi xj if and only if y

55、i yj Example:,x1,x1,x5,x4,x3,x2,y1,y2,y3,y4,y5,59,Definition of Matching Processors,Processors pi in R1 and pj in R2 are matching if they are the same distance from the processor with minimum id. Example: p0 (with id 18) in R1 and p1 (with id 5) in R2, which are 2 hops from p3 (resp., p4),60,Definit

56、ion of Similar Behaviors,Two processors have similar behaviors in two executions if, in every round one processor sends a message to the left (right) if and only if the other one does one processor is elected if and only if the other one is,61,Synchronous Lower Bound,Theorem (3.18): For every n 8 th

57、at is a power of 2, there is a ring of size n on which any synchronous comparison-based algorithm sends (n log n) msgs. Proof: For each n, construct a highly symmetric ring Sn on which every comparison-based algorithm takes lots of messages. Symmetry means many processors have order-equivalent neigh

58、borhoods and thus behave similarly (including sending msgs),62,Proof Strategy,Define highly symmetric ring Sn Show that the number of active rounds is at least n/8 Show that in the k-th active round, at least n/(2(2k+1) msgs are sent. Do some arithmetic to show that n/(2(2k+1) = (n log n),k=1,n/8,CP

59、SC 668,Set 5: Synchronous LE in Rings,63,Active Rounds,A round is active if at least one processor sends a msg A proc. in a synchronous algorithm can potentially learn something even in an inactive round cf. the simple synchronous alg But in a comparison-based alg., a proc. cant learn about the order pattern of its ring in an inactive round Note that the k-th active round might be much later than the k-th round,64,A Highly Symmetric Ring Sn,Let pi s id be rev(i) , the integer whose binary representation using log n bits is the reverse o