CS514: Intermediate Course in Operating SystemsRECAP: Agreement ProtocolsWhen is agreement needed?FLP was about agreementWe don’t always need the FLP “version” of agreementSlide 6More needs for agreementOne protocol isn’t enough!Agreement: ParadigmsThings we knowWhat about real systems?Real world goals?Performance goalsOther goalsRoadmapSlide 16Historical asideSlide 18Historical AsideNames of some famous systemsWe’re already on track “A”The commit problemAs a time-line pictureObservations?Slide 25In fact we’re missing stuffFault toleranceSlide 28Initiator fails, members healthyIdeas?Leads to two ideasProblems?Slide 33Why do we get stuck?Why not always have a log?3 phase commitSlide 37Why 3 phase commit?Value of 3PC?State diagram for non-faulty memberSome additional detailsWhat next?LayeringBut first…What should you be reading?CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TARECAP: Agreement ProtocolsThese are used when a set of processes needs to make a decision of some sortThe problem arises often and can take many formsAn agreement protocol solves a simple (single-bit) instance of the general problemGives us a “template” for building fancier protocols that solve other problemsWhen is agreement needed?Recall Sam and Jill from lecture 5Sam was hoping he and Jill could eat outside but they couldn’t get their act together and ended up eating insideIt illustrated a type of impossibility result:Impossible to learn new “common knowledge” facts in an asynchronous distributed systemDefn: “I know that you know that I know…” without any finite limit on the chainFLP was about agreementThere we focused on agreement on the value of a single bitWe concluded thatOne can build decision protocolsAnd prove that they decide correctlyAnd can even include failure handlingBut they can’t guarantee progressIf if we have many processes and know that at most one of them might crashWe don’t always need the FLP “version” of agreementSam and Jill needed an impossible-to-achieve form of agreement!Had they sought a weaker guarantee they might have been able to eat outside without risk!For example: suppose Sam sends “Let’s eat outside” and Jill replies “Sounds good,” and Sam replies “See yah!”3-way handshake has risk built in (if the last message doesn’t get through, what to do?) but the risk isn’t large. If they can live with that risk… it solves the problemFLP is about impossible “progress” propertiesWhen is agreement needed?Situations where agreement arisesOrdering updates to a replicated data itemMight allow concurrent updates from sources that don’t coordinate their actionsOr could have updates that are ordered by, say, use of locking but that might then get disordered in transmission through the networkDecision on which updates “occurred”An issue in systems that experience faultsMore needs for agreementAgreement on the membershipAgreement on the leader, or some other process with a special roleAgreement on a rankingAgreement on loads or other inputs to a load balancing serviceAgreement on the mapping of a name to a target IP address, or on routingOne protocol isn’t enough!We’ll need different solutions for these different agreement problemsBut if we abstract away the detail can learn basic things about how such protocols should be structuredAlso can learn to prove correctnessThen can build specific specialized ones, optimized for a particular use and engineered to perform wellAgreement: ParadigmsWe’ve already seen two examplesFLP involved consensus on a single bitProcesses have a bit values 0 or 1Protocol executesOutcome: all agree on a value (and it was a legitimate input, and they tolerate faults, and we are faithful to the decisions of the dead)Byzantine Agreement: same idea; different modelBut paradigms are about clean theory. Engineering implies a focus on speed!Things we knowFrom FLP we know that this statement of the problem…… can be solved in asynchronous settings… but solution can’t guarantee livenessThere is at least one input scenario and “event sequence” that prevents progressFrom BA, we know that in a system with synchronized rounds, solutions can be found, but they are costlyAnyhow, that synchronous model is impracticalWhat about real systems?Real world is neither synchronous nor asynchronousWe’ve got a good idea of messages latency… and pretty good clocksLike Sam and Jill, we may be able to tolerate undesired but unlikely outcomesAnyhow, no real system can achieve perfect correctness (at best we depend on the compiler, the operating system)Real world goals?Practical solutions that:Work if most of the system is workingTolerate crashes and perhaps even some mild forms of “Byzantine” behavior, like accidental data corruption“Strive to be live” (to make progress) but accept that some crash/partitioning scenarios could prevent this, like it or notWe still want to be rigorousPerformance goalsWant solutions that are cheap, but what should this mean?Traditionally: low total number of messages sent (today, only rarely an important metric)Have low costs in per-process messages sent, received (often important)Have low delay from when update was generated to when it was applied (always VERY important)Other goalsNow we’ll begin to work our way up to really good solutions. These:Are efficient in senses just outlinedAre packaged so that they can be used to solve real problemsAre well structured, so that we can understand the code and (hopefully) debug/maintain it easilyRoadmapTo do thisFirst look at 2-phase and 3-phase commitThis pattern of communication arises in many protocols and will be a basic building blockNext look at “agreeing on membership”Protocols that track membership give fastest update rates, often by orders of magnitude!Then, implement an ordered update (or multicast) over these mechanismsFinally, think about software architecture issuesRoadmapThis will give usA notion of a “process group”Has a name… and a set of members… and the system can dynamically track membershipMembership ranking is useful in applicationsWays to do ordered, reliable, multicast Things built over these primitives: leader
View Full Document
Unlocking...