CS514: Intermediate Course in Operating SystemsReminder: Group CommunicationRecipe for a group communication systemRole of GMSGroup picture… with GMSGroup membership serviceIssues?Slide 8Slide 9ApproachGMP exampleFailure detection: may make mistakesBasic GMPSlide 14Special concerns?What if leader fails?Slide 17Properties of GMPUse of GMSProcesses t and u “using” a GMSWe have our pie shellUnreliable multicastConcerns if sender crashesAn interrupted multicastFlush protocolHow to do this?Slide 27Event orderingState transferState transfer and reliable multicastWhat about ordering?Preview of coming attractionsCS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TAReminder: Group CommunicationTerminology: group create, view, join with state transfer, multicast, client-to-group communicationThis is the “dynamic” membership model: processes come & gopqrstuRecipe for a group communication systemBack one pie shellBuild a service that can track group membership and report “view changes”Prepare 2 cups of basic pie fillingDevelop a simple fault-tolerant multicast protocolAdd flavoring of your choiceExtend the multicast protocol to provide desired delivery ordering guaranteesFill pie shell, chill, and serveDesign an end-user “API” or “toolkit”. Clients will “serve themselves”, with various goals…Role of GMSWe’ll add a new system service to our distributed system, like the Internet DNS but with a new roleIts job is to track membership of groupsTo join a group a process will ask the GMSThe GMS will also monitor members and can use this to drop them from a groupAnd it will report membership changesGroup picture… with GMSpqrstuGMSP requests: I wish to join or create group “X”.GMS responds: Group X created with you as the only memberT to GMS: What is current membership for group X?GMS to T: X = {p}r joins…GMS notices that q has failed (or q decides to leave)Q joins, now X = {p,q}. Since p is the oldest prior member, it does a state transfer to qGroup membership serviceRuns on some sensible place, like the server hosting your DNSTakes as input:Process “join” eventsProcess “leave” eventsApparent failuresOutput:Membership views for group(s) to which those processes belongSeen by the protocol “library” that the group members are using for communication supportIssues?The service itself needs to be fault-tolerantOtherwise our entire system could be crippled by a single failure!So we’ll run two or three copies of itHence Group Membership Service (GMS) must run some form of protocol (GMP)Group picture… with GMSpqrstGMSGroup picture… with GMSpqrstGMS0GMS1GMS2Let’s start by focusing on how GMS tracks its own membership. Since it can’t just ask the GMS to do this it needs to have a special protocol for this purpose. But only the GMS runs this special protocol, since other processes just rely on the GMS to do this jobIn fact it will end up using those reliable multicast protocols to replicate membership information for other groups that rely on itThe GMS is a group too. We’ll build it first and then will use it when building reliable multicast protocols.ApproachWe’ll assume that GMS has members {p,q,r} at time tDesignate the “oldest” of these as the protocol “leader”To initiate a change in GMS membership, leader will run the GMPOthers can’t run the GMP; they report events to the leaderGMP exampleExample:Initially, GMS consists of {p,q,r}Then q is believed to have crashedpqrFailure detection: may make mistakesRecall that failures are hard to distinguish from network delaySo we accept risk of mistakeIf p is running a protocol to exclude q because “q has failed”, all processes that hear from p will cut channels to qAvoids “messages from the dead”q must rejoin to participate in GMS againBasic GMPSomeone reports that “q has failed”Leader (process p) runs a 2-phase commit protocolAnnounces a “proposed new GMS view”Excludes q, or might add some members who are joining, or could do both at onceWaits until a majority of members of current view have voted “ok”Then commits the changeGMP exampleProposes new view: {p,r} [-q]Needs majority consent: p itself, plus one more (“current” view had 3 members)Can add members at the same timepqrProposed V1 = {p,r}V0 = {p,q,r}OKCommit V1V1 = {p,r}Special concerns?What if someone doesn’t respond?P can tolerate failures of a minority of members of the current viewNew first-round “overlaps” its commit:“Commit that q has left. Propose add s and drop r”P must wait if it can’t contact a majorityAvoids risk of partitioningWhat if leader fails?Here we do a 3-phase protocolNew leader identifies itself based on age ranking (oldest surviving process)It runs an inquiry phase“The adored leader has died. Did he say anything to you before passing away?”Note that this causes participants to cut connections to the adored previous leaderThen run normal 2-phase protocol but “terminate” any interrupted view changes leader had initiatedGMP exampleNew leader first sends an inquiryThen proposes new view: {r,s} [-p]Needs majority consent: q itself, plus one more (“current” view had 3 members)Again, can add members at the same timepqrProposed V1 = {r,s}V0 = {p,q,r}OKCommit V1V1 = {r,s}Inquire [-p]OK: nothing was pendingProperties of GMPWe end up with a single service shared by the entire systemIn fact every process can participateBut more often we just designate a few processes and they run the GMPTypically the GMS runs the GMP and also uses replicated data to track membership of other groupsUse of GMSA process t, not in the GMS, wants to join group “Upson309_status”It sends a request to the GMSGMS updates the “membership of group Upson309_status” to add tReports the new view to the current members of the group, and to tBegins to monitor t’s healthProcesses t and u “using” a GMSThe GMS contains p, q, r (and later, s)Processes t and u want to form some other group, but use the GMS to manage membership on their behalfpqrstuWe have our pie shellNow we’ve got a group membership service that reports identical views to all members, tracks healthCan we build a reliable multicast?Unreliable multicastSuppose
View Full Document