Distributed Systems
Vanilla Consensus Problem
l N processes {0, 1, 2, … n-1}
Copyright By PowCoder代写 加微信 powcoder
l Each process proposes its own initial value in an agreed domain
l Crash Fault might occur
l In the end, every process agrees upon an irrevocable final decision value l The losers are discarded
l Agreement: that value of a nonfaulty process must be identical to other nonfaulty processes
l Termination: every nonfaulty process must reach a decision of its final value l Liveness
l Validity: just a sanity check. If every nonfaulty process begins with the same initial value v, then their final decision must be v (i.e., it’s silly to find another value to agree on that reflects nobody’s initial choice)
Specialized Consensus Problems
l Leader Election
l Finaldecisionvalue–everyprocessagreesonthesameleaderid
l Distributed Transaction
l Sharding(Partitioning)butnotReplication
l Transfer$100frommyCAbranchtoNYbranch l Atomicity: Commit or Abort (all or nothing)
l Consensusonwhat?
n Value = {commit, abort} n CA commit, NY commit n CA abort, NY abort
n All or nothing
l Agreement Problem
l Single Proposal (everybody agrees to go McDonald?) yes / no only
l Aclientsubmits‘put(x=7)’,allreplicasagree/disagreeaboutit
Hardness of Consensus Problem
l Asynchronous System
l Crash Failure can’t be accurately identified (no way to differentiate a slow process and a die
l FLP Theorem [Journal of ACM 85]
n “Impossible to have a (deterministic) protocol that solves consensus in a message-passing ascynchronous system in which at most 1 process may crash-fail”
n Hence, it also extends to the hardness of complete vs. accurate in failure detection n Baseline algorithm when no faulty processes
l Everybody sends its own v to all others
l Let the collection be V (and currently we have no malicious case yet) l Everyone gets the same V
l Everyone applies a function f on V
l Example f can be the majority (as long as it is deterministic) l Agreement done!
Intuition of FLP theorem
l At first glance it might be counter-intuitive l N processes and take majority:
n000000000000011
l So if is gone, nothing hurt.
l But FLP is a theorem, talking about the corner/worst case: n0001111
l If the faulty process is gone, then it hurts!
Hardness of Consensus Problem
l Asynchronous System
l Impossibility of distributed consensus with one faulty process
l If just crash-fault is impossible, dealing with Byzantine faults would be even more impossible
l Synchronous System l Byzantine fault
n A.k.a. Byzantine Generals Problem
l Impossibe when # of processes n <=3 and malicious process f = 1 l In other words, possible when n > 3 when f = 1
n Cast it as n generals, find an agreed time to attack all together or else leads to defeat
Byzantine Generals Problem (remember: sync mode)
l Traitors might:
l Not responding
l Send conflicting messages to hinder the agreement l No one know who the traitors are
Byzantine Generals Problem
l N generals
l Any general can send message {attack 1 or retreat 0}
l Agreement:
l every loyal general gets the same set of S of messages, apply the same function (e.g.,
majority) to decide the final strategy
l Agreement problem means: only one proposes a value (not everybody proposes her own value at the same time)
l When publishing, the general is playing the role of the unique/one commander
l When receiving, the general is playing the role of a lieutenant
l Consistency Requirements (named as “interactive consistency”):
l IC1: All loyal receivers (lieutenants) receive the same message from the same sender
n èit doesn’t rule out the awkward case of the commander sends out “Attack” but all loyal receivers receive the same “Retreat” message
l IC2: If a sender (commander) is loyal, every loyal receiver receives his order
BGP settings
l Communication channel is “Oral Message” l Messages are not corrupted in transit
n (loyal messenger; though the message itself can be wrong because of the bad sender) l Messages can be lost, but absence of message can be detected (=synchrony!)
l When a message is received (or its lost is detected)
n the receiver knows who is the sender of that message
Byzantine General Problem
l Using oral message, impossibe when
l # of processes n <=3 and malicious process f = 1
l Generalizable to: using oral message, impossible when l # of processes n <=3f and f traitors (f>0)
l Why highlight oral message?
n If the commander can write and sign the message, case (a) is gone
Lamport et al “Oral Message” algorithm
l As a lieutenant, if I am smart, before I attack, I might want to check if other lieutenants (receivers) receive the same messages as mine
l So, everyone forwards its received messages to the others
l Hence, there are two kinds of messages:
l Direct message: received from the commander directly
l Indirect message: 2nd hand message received from the other lieutenants about the commander’s messages
Lamport et al ACM TOPLAS 82 OM(f) algorithm
l A Recursive algorithm:
l fissetasthenumberoftraitors
l Thehigherf,morerecursivelevelsareneeded
l OM(0) //base case
l Commanderisendsoutv(0or1)toeverylieutenantj(j!=i) l Eachlieutenantjacceptsthevaluefromi
n As f=0 in this case l OM(f) //3 phases, for f=1
1) The commander i sends out a value v (0 or 1) to every lieutenant j (j!=i) 2) Each lieutenant j who receives v
n Recursive call OM(f-1) as a new commander to forward v to the other lieutenants (but not i)
n //All (honest) lieutenants would do this, hence outvotes the malicious ones 3) Each lieutenant j, receives (n-1) values in total:
n 1 value directly from commander i’s OM(f)) //from step 1
n n-2 indirect values from n-2 lieutenants j.OM(f-1) //from step 2 n Each lieutenant uses the majority of the (n-1) values
l If a value is not received, assume that as ‘retreat’
l 4 Generals
l 1 of them is traitor
l Majority decision function
For f>1 (need to adjust the rules – e.g., takes majority from multiple values from the same commander)
1 & 3 no response; Each other: OM(f-1)
Ghosh’s book
l Setting: Byzantine
l Weakly-sync algorithm
l Use of crypto (message authentication) to solve Byzantine
l Guarantees liveness when weakly sync holds (i.e., the network behaves normally)
l Setting: no Byzantine
l No 100% guarantees of liveness (though guarantees liveness with high probability)
l That is, it works correctly under partial synchrony
l Whennetworkisnormal n It is safe
n It provides liveness l It terminates
l Whennetworkisabnormal n It is still safe
n It may give you liveness and terminate after the network is back to normal l The protocol attempts to make progress even
l duringperiodswhensome(boundednumber)ofnodesareunresponsive
l There is also a mechanism to support configuration changes l dropapermanentlyfailedreplicaortoaddanewreplica
l First by Lynch et al. [But no proof]
l Lamport’s Part-Time Parliament Paper [Protocol + Proof]
l “Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. suggested the name Paxos for the island.”
l “I submitted the paper to TOCS in 1990. All three referees said that the paper was mildly interesting, though not very important, but that all the Paxos stuff had to be removed. I was quite annoyed at how humorless everyone working in the field seemed to be, so I did nothing with the paper.”
l Real systems began using Paxos, follow-on papers were appearing, so TOCS reconsidered the same paper and got accepted in 1998 [8 years!]
l Let’s consider this naive protocol:
l Phase 1: Send a command to all replicas
l Phase 2: Send Commit if all replicas said ok l What’s the problem?
n It violates the fault-tolerance first-principle l # of faulty nodes f=1?
l It halts (no progress; liveness)
l So, similar to Byzantine Generals, a node can wear one of the 3 hats at anytime:
l Proposer: propose a command, e.g., S1: put(x=17); S2: put(x=18)
l Acceptor (Voter): accept/reject a proposal, e.g., S3 accepts S1’s proposal, turn down S2’s l Learner: learn (get) an accepted proposal and apply it
l Each instance: one proposal (command) reaches consensus l Next command? Starts a new Paxos instance
l 4 proposers -> 4 different proposals (note: they can propose the same value) l Try to reach consensus //i.e., more than an agreement problem
l Multiple voters/acceptors (for fault-tolerance)
l Naturally, each voters can cast 1 vote n yes for only one proposal
n no for rest (reject the rest)
l Decision based on the > 1⁄2 majority votes
One challenge of General Consensus
l 3 proposals (v1, v2, v3), 3 acceptors l Can’t reach majority that easy
n s1 votes for v3 n s2 votes for v2 n s3 votes for v1
l No proposal gets enough majority and all get rejected
l Before we begin, remember
1. The parliament story is just a “bad” analogy (that’s why reviewers didn’t like that much and
people didn’t understand it)
2. There are no bad guys
3. Everyone just wants to get the consensus ASAP indeed (efficiency)
l Phase 1: [leader election] l A) Prepare
l B) Promise
l Phase 2: [consensus within majority] l A) Accept
l B) Accepted
l Proposer
l Whoeverinterestedinproposingavaluesendsouta
number N to all voters in attempt to be a leader; //only becoming a leader can propose new value l Voter
1a) Prepare Phase
1b) Promise Phase
IF N > m //”hi candidate leader” [where m is max of proposal # that I have ever received] n If I have already Accepted (Phase 2b) a proposal value u
l I reply with a Promise(m, u) message //”sorry, I have already accepted u, you better help continue on u first“ n Else //”I promise that I would ignore any received/future proposal (of this Paxos instance) that is
l Send Accepted(v) ack message to the Proposer*
n Else //i.e., in the meantime, a new and higher proposal number has arrived to me (probably someone else
finds the new leader is also dead…) l Ignore this Accept Message
l Proposer (Leader)
l Iftheleaderreceives“Accepted”messagefromthemajorityofvoterswiththesameproposalnumberN n Consensus is reached and the value is regarded as ‘committed’
n Notify the learners to Accepted v*
* To improve latency, many implementations change it to: • the voter also sends Accepted(v) to all learners straight
(in addition to ack back to the proposer)
• and let each learner counts the majority locally itself
(instead of letting the proposer to count the majority and notify the learners**) èSave one round-trip
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com