1CS514: Intermediate Course in Computer SystemsLecture 14: Oct. 15, 2003Tracking Group Membership (part 2)CS514Coordinator-based membership| All membership events fed through the coordinatorz Coordinator uses 2PC to insure all processes agree on membership| If coordinator fails, oldest active process takes over coordinator rolez Using a 3PC2CS514So first, lets look at 2PC and 3PC| Lets look at 2PC and 3PC “generically”---that is, outside the context of membership protocolsz In fact, we’ll look at 2/3PC assuming a static membership| Then we’ll apply it to membership protocols per seCS514Fundamental idea:| Essentially like running a vote, where unanimity is requiredz I.e., outcome is yes if all vote yesz Outcome is no otherwise| Two phases:z First gather votes from all participantsz Then tell all participants the outcome of the vote3CS514Human example| Say you want to schedule a meeting among a group of peoplez Must find a time when all people can attend---if any one cannot attend, must find another timeCS514Meeting coordinator’s actions:| First ask everyone “can you come at 2:00?”| Wait for replies| If anyone replies ‘no’, tell everybody there is no meetingz abort| If everyone replies ‘yes’, tell everybody there is a meetingz commit4CS514Meeting participant’s actions:| Coordinator asks if you can attend at 2:00| Check your calendarz If your answer is no, tell the coordinator and do nothing else| If your answer is yes, “pencil in” the meeting time, and wait for confirmationz Note that now you cannot commit that meeting time to anyone else!| If meeting confirmed, then commit the meeting time in your calendar| If meeting canceled, then free the meeting time in your calendarCS514Other key concepts in 2/3PC| Resources may be “put on hold” until 2PC protocol completesz Resources are then subsequently either taken or freed| 2PC may occur in parallel or in serialz Latter happens in the context of a “transaction”5CS514Example of 2PC in a transaction| You want to take a trip to the world cup, but you won’t go unless you get:z A flight, a hotel, a rental car, andtickets to a few matches| You tentatively reserve each, and either:z Confirm them all if you get them allz Cancel them all if you fail to get any oneCS5142PC picture6CS5142PC pictureCS514Coordinator algorithm7CS514Participant algorithmCS514Things to consider| These algorithms are simple and clean, but . . .| Don’t consider various failuresz And impact on other processesz Or impact on own garbage collection8CS514Possible points of participant failureCS514Logs allow recovery after failure9CS514Possible points of coordinator failureCS514Logs allow recovery after failure10CS514But require acks from participants to garbage collectCS514And duplicate message detection in participants11CS514This naïve approach leads to lockup| If coordinator crashes, participants cannot release locked up resources| We would at least like to be able to terminate a given 2PC protocol without the coordinatorz Even if we don’t have the ability to elect a new coordinator| Can a participant finish the coordinator role?z Only if it knows the 2PC result (abort or commit)CS514Participant completion of 2PC| Participants that know outcome must wait until it is sure all other participants know outcome| Participants in pre-commit can detect coordinator failure and finish the 2PC protocol12CS514Participant completion of 2PCCS514Post-commit participant has to delay garbage collect13CS514Post-commit participant has to delay garbage collectCS514Final 2PC participant algorithm!14CS514(compare with original naïve algorithm…)CS514Final 2PC coordinator algorithm!15CS514(again, compare with original naïve algorithm…)CS514Coordinator algorithm optimization16CS514Coordinator algorithm optimizationCS5143PC can prevent the coordinator failure lockup| We won’t cover it in classz (or on the final exam)| You can read about it in Ken’s book if you are curious| It is a nice result, but too expensive to do in practice17CS514Coordinator-based membership protocol| Coordinator manages the whole process| Any process can detect failure of another processz Report it to the coordinatorz There is constant keep-alive activity| Any new process can send a join request to the coordinator| Thus, at some point in time, coordinator has a join and leave list, and starts a new viewCS514New view, no coordinator failure| Basically a 2PC| In first phase, coordinator announces the join and leave lists, collects acksz At this point, existing processes “shun” leaving processesz This helps insure that they kill themselves in a fail-stop way (if not already dead)z The coordinator must receive acks from a majority of processes| In the second phase, the coordinator commits the changes18CS514New view, with coordinator failure| If the coordinator is detected as failed, the next oldest process assumes the coordinator role| The new coordinator announces itself, starts collecting acksz At this point, the old coordinator is shunned, and will kill itself if alive| When it has a majority of acks, the new coordinator will start the 2PC of the previous slideCS514Majority of processes fail| To avoid simultaneous partitioned segments operating independently, if a majority of processes fail, a new view cannot be establishedz Alarms go off, and the system must be restarted, essentially by
View Full Document
Unlocking...