Virtual SynchronyPapersBackgroundFail StopMotivationProcess GroupsAnonymous GroupsExplicit GroupsBuilding groups over conventional technologyClose SynchronyA synchronous executionSo… what’s wrong with that?Slide 13A few protocols…Four protocols!?!?Slide 16Single updaterSlide 18Causally ordered updatesSlide 20Slide 21Hey… that sped things up!Slide 23Slide 24Three Round MulticastAs a time-line pictureJust one more…Flush protocolStyles of groupsHistorical AsideNames of some famous systemsSounds good… what’s wrong with it?Stable vs DurableOrdering semanticsThe problem with CATOCSIt can’t say “for sure”It can’t say “together”Stock trading exampleCan’t say the “whole story”It can’t say it efficientlyAnd… what of the end to end argument?Classes of distributed applicationsImplementing only part of the messaging?SemanticsScalabilityBuffering growsGroup membership protocolsWho uses ISIS?ISIS-based utilitiesSlide 50Now… somewhat supported…and people actually use it.An ongoing debateReferencesVirtual SynchronyJustin W. HartCS 61411/17/2005PapersThe Process Group Approach to Reliable Distributed Computing. Birman. CACM, Dec 1993, 36(12):37-53.Understanding the Limitations of Causally and Totally Ordered Communication.6 Cheriton and Skeen.6 14th SOSP, 1993.BackgroundChandy-Lamport Logical ClocksConsistent CutsDistributed SnapshotsPublish/SubscribeFail-StopFail StopGroup Membership ServiceProcesses appear to fail by haltingHow does this affect the FLP result?MotivationInformation BackplaneCustomizationHierarchical StructureFault-ToleranceReliabilityProcess GroupsTypes of groupsAnonymous groupsExplicit groupsImplementation RequirementsGroup communicationGroup membership as inputSynchronizationAnonymous GroupsGroup addressingMessages sent exactly once to all or no recipientsOrderingLoggingExplicit GroupsGroup members cooperate directlyMay execute algorithms based on membership knowledgeCommunication is sensitive to membership changesBuilding groups over conventional technologyConventional message passing technologiesGroup addressingLogical time & causal dependencyMessage delivery orderingState transferFault toleranceClose SynchronyClose Synchrony100% lock-step execution modelA synchronous executionpqrstuWith true synchrony executions run in genuine lock-step.So… what’s wrong with that?Under close synchrony, execution is limited by the slowest process in the group!Virtual SynchronyRelax synchronization requirements where possibleBenefit by allowing for asynchronous interactionsDo this where the result is identical to close synchronyA few protocols…fbcastcbcastabcastgbcastFour protocols!?!?…but Justin. The paper only discussed 2 protocols… you’re getting off-topic!A few protocols…fbcastSimple protocol upon which we’ll build the others.Delivery is FIFO ordered, with respect to the original senderAccomplished easily with a logical timestampcbcastabcastgbcastSingle updaterIf p is the only update source, the need is a bit like the TCP “fifo” orderingfbc ast is a good choice for this caseprst1 2 3 4A few protocols…fbcastcbcastReceipt is causally orderedProtocol in paper uses token passingAnother simple protocol uses vector timestampsabcastgbcastCausally ordered updatesSimple protocol based on token passingCausally ordered updatesExample: messages from p and s arrive out of order at tprstVT(a) = [0,0,0,1]VT(b)=[1,0,0,1]VT(c) = [1,0,1,1]c is early: VT(c) = [1,0,1,1] but VT(t)=[0,0,0,1]: clearly we are missing one message from sWhen b arrives, we can deliver both it and message c, in orderCausally ordered updatesEach thread corresponds to a different lockIn effect: red “events” never conflict with green ones!prst1234512Hey… that sped things up!Now I get it! Processes only have to wait for processes that they depend on. Not the slowest in the group!A few protocols…fbcastcbcastabcastAtomic delivery orderingWith respect to other abcastsMore costly than cbcast, but with a stronger ordering propertyISIS builds abcast over cbcastgbcastA few protocols…fbcastcbcastabcastgbcastAtomic delivery orderingWith respect to everythingThree Round MulticastAs a time-line picture2PC initiatorpqrstVote?All vote “commit”Commit!Phase 1 Phase 2Just one more…Flush protocolWe say that a message is unstable if some receiver has it but (perhaps) others don’tFor example, q’s message is unstable at process rIf q fails we want to “flush” unstable messages out of the systemStyles of groupsPeer GroupsProcesses cooperate closelyClient-Server GroupsGroup acts as a serverClient multicasts repeatedly to the groupDiffusion GroupsGroup serves informationClients connect to receive data from groupHierarchical GroupsOffer scalability through a hierarchy of connected groupsHistorical AsideTwo major classes of real systemsVirtual synchronyWeaker properties – not quite “FLP consensus”Much higher performance (orders of magnitude)Requires that majority of system remain connected. Partitioning failures force protocols to wait for repairQuorum-based state machine protocols areCloser to FLP definition of consensus Slower (by orders of magnitude) Sometimes can make progress in partitioning situations where virtual synchrony can’tNames of some famous systemsIsis was first practical virtual synchrony systemLater followed by Transis, Totem, HorusToday: Best options are Jgroups, Spread, EnsembleTechnology is now used in IBM Websphere and Microsoft Windows Clusters products!Paxos was first major state machine systemBASE and other Byzantine Quorum systems now getting attention from the security community(End of Historical aside)Sounds good… what’s wrong with it?Tries to solve state problems at communication levelThis violates the end-to-end argument!Consistency requirements are typically stated with respect to application stateStable vs DurableStable – messages are buffered until received by all group membersDurable – message will be delivered, even if the sender diesOrdering semanticsIncidental OrderingSemantic OrderingPrescriptive OrderingThe problem with CATOCSIt can’t say “for sure”It can’t