Distributed Systems: Atomicity, Decision Making, Faults, SnapshotsAnnouncementsReview: What time is it?Review: Event OrderingReview: Happens-beforeReview: Total ordering?Review: Partial OrderingReview: Total Ordering?Review: TimestampsReview: Distributed Mutual ExclusionTodayAtomicityE.g. Two-Phase CommitTwo Phase Commit: Phase 1Two Phase Commit: Phase 2PerformanceFailure Handling in 2PC – Replica FailureFailure Handling in 2PC – Coordinator Ci FailureFailure HandlingFailures in distributed systemsImpossibility of ConsensusDistributed Decision Making DiscussionFaultsCategories of failuresSlide 25Slide 26Categories of failureModels of failureTwo kinds of modelsAdding failures in Lamport’s modelWhat about the synchronous model?Neither model is realisticFischer, Lynch and PattersonTougher failure modelsHere the situation is much harderByzantine Generals scenarioSlide 37A timeline perspectiveSlide 39What can the traitor do?Outcomes?What can we do?Digital signaturesWith such a systemSlide 45Slide 46Traitor is stymiedDistributed SnapshotsIntroducing “wall clock time”Synchronizing clocksSlide 51Slide 52Consequences?Temporal distortionsSlide 55Slide 56Slide 57Slide 58Slide 59Consistent cuts and snapshotsSlide 61Slide 62Who cares?Deadlock detection “algorithm”Suppose we detect this statePhantom deadlocks!Slide 67Chandy/Lamport AlgorithmUsing logical clocks to make cutsSlide 70Turn idea into an algorithmChandy/LamportSlide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86What’s in the “state”?SummarySlides adapted from Ken's CS514 lecturesDistributed Systems: Atomicity, Decision Making, Faults, Snapshots2Announcements•Prelim II coming up next week:–In class, Thursday, November 20th, 10:10—11:25pm–203 Thurston–Closed book, no calculators/PDAs/…–Bring ID•Topics:–Everything after first prelim–Lectures 14-22, chapters 10-15 (8th ed)•Review Session Tonight, November 18th, 6:30pm–7:30pm–Location: 315 Upson Hall3Review: What time is it?•In distributed system we need practical ways to deal with time–E.g. we may need to agree that update A occurred before update B–Or offer a “lease” on a resource that expires at time 10:10.0150 –Or guarantee that a time critical event will reach all interested parties within 100ms4Review: Event Ordering•Problem: distributed systems do not share a clock–Many coordination problems would be simplified if they did (“first one wins”)•Distributed systems do have some sense of time–Events in a single process happen in order–Messages between processes must be sent before they can be received–How helpful is this?5Review: Happens-before•Define a Happens-before relation (denoted by ).–1) If A and B are events in the same process, and A was executed before B, then A  B.–2) If A is the event of sending a message by one process and B is the event of receiving that message by another process, then A  B.–3) If A  B and B  C then A  C.6Review: Total ordering?•Happens-before gives a partial ordering of events•We still do not have a total ordering of events–We are not able to order events that happen concurrently•Concurrent if (not AB) and (not BA)7Review: Partial OrderingPi ->Pi+1; Qi -> Qi+1; Ri -> Ri+1R0->Q4; Q3->R4; Q1->P4; P1->Q28Review: Total Ordering?P0, P1, Q0, Q1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R4P0, Q0, Q1, P1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R4P0, Q0, P1, Q1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R49 Review: Timestamps•Assume each process has a local logical clock that ticks once per event and that the processes are numbered–Clocks tick once per event (including message send)–When send a message, send your clock value–When receive a message, set your clock to MAX( your clock, timestamp of message + 1) •Thus sending comes before receiving•Only visibility into actions at other nodes happens during communication, communicate synchronizes the clocks–If the timestamps of two events A and B are the same, then use the process identity numbers to break ties. •This gives a total ordering!10Review: Distributed Mutual Exclusion•Want mutual exclusion in distributed setting–The system consists of n processes; each process Pi resides at a different processor–Each process has a critical section that requires mutual exclusion–Problem: Cannot use atomic testAndSet primitive since memory not shared and processes may be on physically separated nodes •Requirement–If Pi is executing in its critical section, then no other process Pj is executing in its critical section •Compare three solutions•Centralized Distributed Mutual Exclusion (CDME)•Fully Distributed Mutual Exclusion (DDME)•Token passing11Today•Atomicity and Distributed Decision Making•Faults in distributed systems•What time is it now?–Synchronized clocks•What does the entire system look like at this moment?12Atomicity •Recall: –Atomicity = either all the operations associated with a program unit are executed to completion, or none are performed. •In a distributed system may have multiple copies of the data –(e.g. replicas are good for reliability/availability)•PROBLEM: How do we atomically update all of the copies?–That is, either all replicas reflect a change or none13E.g. Two-Phase Commit•Goal: Update all replicas atomically–Either everyone commits or everyone aborts–No inconsistencies even in face of failures–Caveat: Assume only crash or fail-stop failures•Crash: servers stop when they fail – do not continue and generate bad data•Fail-stop: in addition to crash, fail-stop failure is detectable.•Definitions–Coordinator: Software entity that shepherds the process (in our example could be one of the servers)–Ready to commit: side effects of update safely stored on non-volatile storage•Even if crash, once I say I am ready to commit then a recover procedure will find evidence and continue with commit protocol14Two Phase Commit: Phase 1•Coordinator send a PREPARE message to each replica•Coordinator waits for all replicas to reply with a vote•Each participant replies with a vote–Votes PREPARED if ready to commit and locks data items being updated–Votes NO if unable to get a lock or unable to ensure ready to commit15Two Phase Commit: Phase 2•If coordinator receives PREPARED vote from all replicas then it may decide to commit or abort•Coordinator send its