Group CommunicationDistr. programming is hardKinds of Distributed AppsCommonalityBasic operationsProgramming ExampleProgramming Example, cont’dWhat can go wrong?Example 1: Replicated ServiceExample 2: Parallel ComputationMaking life easierSome TerminologyEventsGraphical representationTraces and PropertiesProtocolsProtocols may be layeredFor example: ReliabilityFor example: Total OrderOther examplesDependenciesToolkits here at CornellTypical protocol stackEach layer adds headerExtreme example app: Replicated State MachineWhat we wantWhat we don’t wantWhat we need: Virtual SynchronyExample: replicated integerExample cont’dWhat is a correct process?Reliability revisitedView ConsensusFailure DetectionMessage OrderingsView OrderingWhy is all this good?Useful for lots of stuffGroup CommunicationRobbert van RenesseCS614 – Tuesday Feb 20, 2001Distr. programming is hard•True concurrency•No shared memory•No locks•Host failures & recoveries•Network failures•Too many scenarios to wrap your brain around•Coordination hard to achieveKinds of Distributed Apps•Replicated Services•Parallel Computing•Factory Floor Control•Management Services•Cluster Services•Distributed Games•…Commonality•Each requires coordination between distributed, possibly flaky components over a possibly flaky network•Each involves a dynamic group of processes communicating with one anotherBasic operations•JoinGroup(“group”, event-handler)–Events:•Point-to-Point and multicast messages•Member Join and Leave (Crash) events•SendP2P(“group”, member-id, message)•Multicast(“group”, message)•LeaveGroup(“group”)Programming ExampleMain(){char buf [ BUF_SIZE ];group = JoinGroup(“chat”, EventHandler);while (read(buf) != EOF) {Multicast(group, buf);}}Programming Example, cont’dEventHandler(event){switch (event.type) {case VIEW: printf(“New view: %v”, event.view); break;case DATA: printf(“%s: %s”, event.source, event.data);}}What can go wrong?•Message M gets delivered to X but not to Y–Lack of agreement on delivery•M1 gets delivered before M2 at X, but the other way around at Y–Lack of order on delivery•X thinks Z is up, while Y thinks Z is down–Lack of agreement on membership lack of coordination programmer has to consider many scenariosExample 1: Replicated Service•Updates are multicast•Lack of agreement on delivery of messages can cause an update to be applied to only some of the replicas•Lack of order on delivery of messages can cause updates to be applied in different orders at different replicasExample 2: Parallel Computation•Membership  Partitioning of task•Lack of agreement on membership  Different processes partition the task differently  Too little or too much work is doneMaking life easier•Reduce the number of possible scenarios by supporting network protocols that guarantee–Agreement of message delivery–Order of message delivery–Agreement of membership updates–Order of membership updates•Results in fewer things to think aboutSome Terminology•Group: a set of processes•Member: a process in the group•View: a uniquely identified set of members as seen by one or more group members–View should approach reachable set of members–Members install new views over time–Each installed view of a group member always includes itself–A member never installs the same view twiceEvents•A group member observes the following events:–Join()–Leave()–Crash()–View-Change(view)–Send-Multicast(msg)–Receive-Multicast(msg, sender)(We ignore multiple groups and point-to-point traffic for the rest of today)Graphical representationMessageLossCrashJoinView ChangeTIMEMemberTraces and Properties•Trace: history of events–E.g.: X sends msg4, Y receives msg3, X gets view3, Y receives msg4, X gets view3, …•Property: predicate on potential traces–E.g.: Messages are delivered in the order they were sent–E.g.: Messages sent are eventually delivered to all correct processesProtocols•Properties are implemented by protocols•Each protocol is a layer of software•Syntax the same for each layer:–Join(), Send-Multicast(), …–Snap together like Lego blocks•Semantics different:–Unreliable  Reliable–Unordered  Ordered–…Protocols may be layeredSeqno layerFIFOtotalunreliableToken layerFor example:SeqnoTokenSTACKFor example: Reliability•Property: A message that is sent is eventually delivered to all correct processes•Protocol: ack/timeout/retransmissionFor example: Total Order•Property: if two processes deliver the same two messages, they deliver them in the same order•Protocol: centralized sequencer, or rotating token, or …Other examplesProperty ProtocolFIFO order Sequence numberBound on resource use Flow ControlConfidentiality EncryptionIntegrity ChecksumConsensus on MembershipMembershipFailures are detected Heartbeat… …Dependencies•Total ordering protocols typically depend on reliable delivery: layer ordering protocol on top of reliability protocolToolkits here at Cornell•Horus and Ensemble are both protocol stack toolkits, each supplying dozens of protocol layers for group communication•Plug’n’play allows applications to choose just those protocols that they require, rather one-size-fits-all•Good performance and flexibilityTypical protocol stackTOTAL ORDERINGMEMBERSHIPFLOW CONTROLRETRANSMISSIONCHECKSUMUDP/IPEach layer adds headerExtreme example app:Replicated State Machine•Model of replicated service:–Each replica is a state machine–Initial state is the same–They receive the same update messages–They receive them in the same order keeps replicas in the same stateWhat we wantState TransferWhat we don’t wantNo orderMessageLossInconsistent ViewWhat we need:Virtual Synchrony•Introduced by Ken Birman / Isis project•Agreement and Ordering of messages•State Transfer•Failure Detection•Discovery of New Members •Consensus on viewsExample: replicated integerint X;Main(){Join(EventHandler);for (;;) {client := receive(ClientRequest);switch (ClientRequest.type) {case ReadInt: reply(client, X);case WriteInt: multicast(ClientRequest.value);}}}Example cont’dEventHandler(event){switch (event.type) {case View: /* nothing */ break;case Update: X := event.value; break;case GetState: return X;case PutState: X := event.state; break;}}What is a correct process?•Many properties talk about correct processes, but what