CS 425/ECE 428/CSE424 Distributed Systems (Fall 2009)AcknowledgementAdministrative Plan for TodayFailure ModelsFailure ModelsDefinition of Consensus (C) Problem Consensus for three processesByzantine Generals (BG) Problem Interactive Consistency (IC) Problem C to BG to ICSolving C with RTO-multicastConsensus in Synchronous Systems Consensus in a synchronous system Dolev & Strong (1983) Examples Correctness of Dolev & Strong AlgorithmByzantine Generals in Synchronous Systems BG in Synchronous System Impossibility (no solution) with N = 3, f = 1Impassibility with N ≤ 3f (outline) BG Algorithm for N = 3f + 1SummaryCS 425/ECE 428/CSE424Distributed Systems(Fall 2009)Lecture 9Consensus ISection 12.5.1-12.5.3Klara NahrstedtAcknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • MP1 posted September 8, Tuesday– Deadline, September 25 (Friday), 4-6pm DemonstrationsPlan for Today• Failure Models• Three Problems – Consensus– Byzantine Generals– Interactive Consistency • Synchronous SettingFailure Models• Crash failure: ceases to execute– Permanent– Cause:, e.g., power loss– Variant: dead for finite period of time then resumes• Omission failure: process or communication channel fails to perform actions that it is supposed to do.– Communication Omission failure: sender sends a sequence of messages but receiver does not receive some subset of messages» Cause: e.g., interference in medium – Process Omission failures: crash failure• Timing failures– Messages do not arrive in time, computation takes longer then expected times– Cause: e.g., congestion, over-loading, garbage-collectionFailure Models• Transient failure: process jumps to arbitrary state and resumes normal execution– Cause: e.g., gamma rays• Byzantine failure: arbitrary messages and transitions– Cause: e.g., software bugs, malicious attacksDefinition of Consensus (C) Problem • N processes {0,1,2,…, N-1} try to agree • pibegins in undecided state and proposes value viє D• pi‘s communicate by exchanging values• pisets its decision value di and enters decided state• Requirements– Termination: eventually all correct processes decide» i.e., each correct process sets its decision variable– Agreement : decision value of all correct processes is the same, » i.e., if piand pjare correct and decided , then di= dj– Integrity: if all correct processes proposed v, then any correct decided process has di= vConsensus for three processes1P2P3 (crashes)P1Consensus algorithmv1=proceedv3=abortv2=proceedd1:=proceed d2:=proceedByzantine Generals (BG) Problem • N > 2 generals {0,1, 2, … N-1}• One of the generals is the commander who issues attack or retreat commands to all the other generals• All generals try to agree about whether to attack or retreat• Some generals (including the commander) may be traitors (byzantine) • Requirements: – Termination: all correct generals decide– Agreement: if piand pjare correct and decided then di = dj– Integrity: if commander is correct, then all correct processes decide value issued by commander• If commander is correct, then integrity implies agreementInteractive Consistency (IC) Problem • N processes {0,1,2,…, N-1} try to agree on vector of values• pibegins in undecided state and proposes a value viє D• pi sets its decision value di and enters decided state• Requirements: – Termination: all correct processes decide– Agreement: the decision vector for all correct processes is the same– Integrity: if piis correct, then for any correct process pjdj[i] = viC to BG to IC• How to solve IC from an algorithm for solving BG?– Run BG N times once with each process as commander• How to solve C from an algorithm for IC? – If majority of processes are correct, then solve IC and then apply majority function • How to solve BG using an algorithm for C? – Commander sends proposed value to itself and the other processes which then run C• How to solve RTO (Reliable Total Ordered) –multicast from C and vice-versa, under crash failures only?Solving C with RTO-multicast• All processes form a group• piperforms RTO-multicast (vi, g)• pisets di= mi, where miis the first msg delivered by RTO-multicast – Termination guaranteed by reliable multicast– Agreement and validity by definitely of TO• Solving consensus using basic multicast in the case where up to f processes may crashConsensus in Synchronous SystemsConsensus in a synchronous systemDolev & Strong (1983)Examples Example execution: with No failures (f = 0)Example execution: with f = 2Correctness of Dolev & Strong Algorithm• Termination: finite number of rounds, finite duration of each round• Agreement and integrity– We will prove by contradiction that Vi[f+1] = Vj[f+1]• Suppose Vi[f+1] ≠ Vj[f+1] with f crashesThere is v є Vi[f+1], but v is not in Vj[f+1], hence there is pkthat delivered v to piin round f+1 but crashed before delivering v to pjThere is v є Vk[f], but v not in Vj[f], hence, there is plthat delivered v to pkin round f but crashed before delivering v to pj… all the way back to Vj[1] Proceeding in this way, we infer at least one crash in each of the preceding rounds (i.e., which implies f+1 crashes) But we have assumed at most f crashes can occur and there are f+1 rounds contradiction.Byzantine Generals in Synchronous SystemsBG in Synchronous System • Assumptions– Up to f of N processes may be Byzantine – Synchronous implies» Correct processes can detect absence of messages with timeout, but cannot conclude that sender has crashed • Is BG solvable? – For N = 3f ?– For N = 3, f = 1?Impossibility (no solution) with N = 3, f = 1• Lamport et al (1982) considered three processes with one Byzantine process• No solution to achieve agreement • Example – 1:v means “1 says v”, 2:1:v means “2 says 1 says v”– 2 different scenarios appear identical to p2p1 (Commander)p2p31:v1:v2:1:v3:1:up1 (Commander)p2p31:x1:w2:1:w3:1:xFaulty processes are shown colouredImpassibility with N ≤ 3f (outline) • Pease et al generalized basic impossibility result• Simulation-based argument– Impossibility shown by contradiction– Assume there
View Full Document
Unlocking...