Byzantine !"#$%Trustworthy SystemsA trustworthy systemdoes what you wantnothing else!despite human and operator errorsdespite environmental disruptions despite attacksBasic PL researchProgram correctnessProgram verificationUser interfacesFault toleranceSecurity}}}}The Odd CoupleFault-tolerance SecurityIntegrityAvailabilityIntegrityAvailabilityConfidentialityA working hypothesisModel compromised processes as ByzantineFaulty processes can deviate arbitrarily (maliciously) from specFaulty processes can colludeBuild replicated services that can tolerate (a threshold of) Byzantine failuresOutlineThe Rise and Fall of State Machine ReplicationState Machine ReplicationPaxosByzantine agreementByzantine fault-tolerance can be fast!PBFTThe Emperor is naked...OutlineThe Rise and Fall of State Machine ReplicationState Machine ReplicationPaxosByzantine agreementByzantine fault-tolerance can be fast!PBFTThe Emperor is naked...Rethinking State Machine ReplicationThe principle: separate agreement from executionThe payoffs:lower replication costs/stronger confidentialitySolution: replicate server!The ProblemClients ServerThe Solution1. Make server deterministic (state machine)State machineThe Solution1. Make server deterministic (state machine)2. Replicate serverState machineThe Solution1. Make server deterministic (state machine)2. Replicate server3. Ensure correct replicas step through the same sequence of state transitions ClientsState machineThe Solution1. Make server deterministic (state machine)2. Replicate server3. Ensure correct replicas step through the same sequence of state transitions 4. Vote on replica outputs for fault-tolerance ClientsState machineThe Solution1. Make server deterministic (state machine)2. Replicate server3. Ensure correct replicas step through the same sequence of state transitions 4. Vote on replica outputs for fault-tolerance ClientsVoterState machineA conundrum. . .A: voter and client share fate!Replica CoordinationAGREEMENT: Every non-faulty state machine receives every requestORDER: Every non-faulty state machine processes the requests it receives in the same relative orderAll non-faulty state machines receive all requests in the same orderThe Part-Time ParliamentParliament determines laws by passing sequence of numbered decreesLegislators can leave and enter the chamber at arbitrary timesNo centralized record of approved decrees–instead, each legislator carries a ledgerGovernment 101If a majority of legislators were in the Chamber and no one entered or left the Chamber for a sufficiently long time, then any decree proposed by a legislator would eventually be passedany passed decree would appear on the ledger of every legislatorSuppliesEach legislator receives ledgerpen with indelible inkscratch paperhourglasslots of messengersBack to the futureA set of processes that can propose valuesProcesses can crash and recoverProcesses have access to stable storageAsynchronous communication via messagesMessages can be lost and duplicated, but not corruptedThe Game: ConsensusSAFETYOnly a value that has been proposed can be chosenOnly a single value is chosenA process never learns that a value has been chosen unless it has beenLIVENESSSome proposed value is eventually chosenIf a value is chosen, a process eventually learns itThe PlayersProposersAcceptorsListenersChoose a value…1. A single acceptorChoose a value…1. A single acceptor2. A majority of acceptors (forces a single value)Choose a value…1. A single acceptor2. A majority of acceptors (forces a single value)When should an acceptor accept?Choose a value…1. A single acceptor2. A majority of acceptors (forces a single value)When should an acceptor accept?!Acceptors must accept first received proposalAcceptors must accept multiple proposalsChoose a value…1. A single acceptor2. A majority of acceptors (forces a single value)When should an acceptor accept?!Acceptors must accept first received proposalAcceptors must accept multiple proposals(pid,value)…a unique value…"If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v…a unique value…"If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v"If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v…a unique value…"If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v"If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v!+"=trouble…a unique value…"If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v"If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v"If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v…and only a unique value"If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v"For any v and n, if a proposal with value v and pid n is issued, then there is a majority-set S of acceptors such that one of the following holds:a. no acceptor in S has accepted any proposal numbered less than nb.v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by acceptors in S Say I do: The proposer’s protocol1. A proposer chooses a new n and sends <prepare,n> to each member of some set of acceptors, asking to respond with:a. A promise never again to accept a pid less than n, andb. The accepted proposal with highest pid less than n if any.2. If proposer receives a response from a majority of acceptors, then it can issue <accept(n,v)> where v is the value of the highest pid among the responses, or is any value selected by the proposer if responders returned no proposalsSay I do: The acceptor’s protocol1. Always respond to prepare messages2. Respond to <accept(n,v)> iff it has not responded to <prepare,n’> with n’ > n !3. Write intended response to stable storage before sending itNote that ! !The Learning Channeli. Each acceptor informs each learnerii. Acceptors contact a distinguished learner, which informs other learnersiii. Acceptors contact a set of learners…Don’t stop me nowLiveness (surprise!) is not guaranteed:n1 < n2 < n3 < n4 <
View Full Document
Unlocking...