CS 425/ECE 428/CSE424 Distributed Systems (Fall 2009)AcknowledgementAdministrative Re-Visit Snapshot ExampleHistorical Comparison of Distributed Mutual Exclusion AlgorithmsHistorical Comparison of Distributed Mutual Exclusion AlgorithmsPlan for today Why Election?Assumptions and Requirements Ring Election A Ring-Based Election in ProgressRing-based ElectionExample: Ring Election Modification to Ring Election Example: Ring Election Modified Ring ElectionElection by the Bully Algorithm Election by the Bully Algorithm Example: Bully Election The Bully AlgorithmPerformance of Bully AlgorithmWhat have we Learnt?SummaryCS 425/ECE 428/CSE424Distributed Systems(Fall 2009)Lecture 8Leader ElectionSection 12.3Klara NahrstedtAcknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • MP1 posted September 8, Tuesday– Deadline, September 25 (Friday), 4-6pm DemonstrationsRe-Visit Snapshot ExampleP1P2P3e10e20e23e30e13abMe11,2Me21,2,3MMe14e32,3,4MMe24e31e13Final Recorded Global Snapshot after Chandy-Lamport Marker Algorithm is over: at P1 : {S1: <$90>, channel message ‘,<$20>’)at P2 : (S2: <$80> ,channel message ‘<$30>’) at P3 : (S3: <$70> ,channel message { })We use couple of concepts: (a) reliable multicast of ‘markers’ M, , (b) causal ordering of markers; (c) closed group communicationIf one wants the global snapshot at one place, one could have a coordinator to collect the snapshot states from each process. $100$100$100e10– deduct $10e20– pay to P1 $20e30– pay to P2 $30Historical Comparison of Distributed Mutual Exclusion Algorithms• 1978 – Introduction of logical Lamport clocks and event ordering (Lamport)• 1981 - Ricart and Agrawala – distributed mutual exclusion – Use of Happen-Before relation and Lamport clocks – Bandwidth : » Messages to entry: 2(N-1)» Message to exist: N-1– Client delay » one round trip– Synchronization delay » 1 messageHistorical Comparison of Distributed Mutual Exclusion Algorithms• 1985 – Maekawa - √N distributed mutual exclusion– Bandwidth :» 2√N messages per entry, » √N messages per exit– Client delay: » One round trip time– Synchronization delay: » One round-trip time• 1989 – Raymond – O(log N) distributed mutual exclusion – Bandwidth:» 2D messages per entry (D – longest path length)» D messages per exist – Best case – radiating star topology (D = log N)– Worst case ?–Plan for today • Election algorithms – Ring-based algorithm– Modified ring-based algorithm– Bully algorithmWhy Election?Example 1: Your Bank maintains multiple servers, but for each customer, one of the servers is responsible, i.e., is the leaderExample 2: In the sequencer-based algorithm for total ordering of multicasts,What happens if the “special” sequencer process fails?Example 3: Coordinator-based distributed mutual exclusion: need to elect (and keep) one coordinatorIn a group of processes, elect a Leader to undertake special tasks. Makes the algorithm design easy.But leader may fail (crash)Some process detects thisThen what? Any process can call for an election. A process can call for at most one election at a time. Multiple processes can call an election simultaneously.The result of an election should not depend on which process calls for it.Each process has Variable called elected An attribute value called attr, e.g., id, MAC address, CPUThe non-faulty process with the best (highest) election attribute value (e.g., highest id or address, or fastest cpu, etc.) is elected. Requirement: A run (execution) of the election algorithm must always guarantee at the end: Safety: ∀ P (P’s elected = (q: non-failed process with the best attribute value) or ⊥) Liveness: ∀ election( (election terminates)& ∀ P: non-faulty process, P’s elected is not ⊥ )Assumptions and RequirementsN Processes are organized in a logical ring. pihas a communication channel to p(i+1) mod N. All messages are sent clockwise around the ring. Any process pithat discovers a coordinator has failed initiates an “election” message <i, pi.attr>When a process pjreceives an election message <i, pi.attr>, it compares the attr in the message with its own. If the arrived pi.attr > pj.attr , then receiver pjforwards the message <i, pi.attr>. If the arrived pi.attr < pj.attr and the receiver pjhas not forwarded an election message earlier, it substitutes its own <j, pj.attr> in the message and forwards it. If the arrived pi.attr = pj.attr , then this process’s pj .attr must be the greatest, and it becomes the new coordinator. This process then sends an “elected” message to its neighbor announcing the election result.When a process pireceives an elected message, it sets its variable electedi id of the message. forwards the message if it is not the new coordinator.Ring ElectionA Ring-Based Election in Progress241594332817241Note: The election was started by process 17.The highest process identifier encountered so far is 24.(final leader will be 33)(attr:=id)The worst-case scenario occurs when the counter-clockwise neighbor has the highest attr A total of N-1 messages is required to reach the new coordinator-to-be. Another N messages are required until the new coordinator-to-be ensures it is the new coordinator.Another N messages are required to circulate the elected messages.Ring of N processesRing-based ElectionAssume – no failures happen during the run of the election algorithm• Safety and Liveness are satisfied.What happens if there are failures during the election run?Example: Ring ElectionElection: 2Election: 4Election: 3Election: 4P1P2P3P4P0P51. P2 initiates electionP1P2P3P4P0P52. P2 receives “ election” , P4 diesP1P2P3P4P0P53. Election: 4 is forwarded for ever?May not work when process failure occurs during the election!Consider above example where attr==highest idProcesses are organized in a logical ring.Any process that discovers the coordinator (leader) has failed initiates an “election” message. This is the initiator of the election. The message is circulated around the ring, bypassing failed nodes. Each node adds (appends)
View Full Document
Unlocking...