6.852: Distributed Algorithms Fall, 2009Today’s planBut actually:More on wait-free computabilityConsensus objectsIrreducibility TheoremOpen questionWait-free computability vs. f-fault-tolerant computabilityWait-free computability vs. f-fault-tolerant computabilityAnother consequence: k-consensusBG simulationWhat is a “Problem”?Solving a ProblemRelating two problemsInput translation GOutput translation HCombining the piecesThe BG constructionThe BG constructionHow P simulates PSafe AgreementSafe AgreementSafe consensus implementationCorrectnessLiveness propertiesBack to the BG simulationWhere are we?BG simulationThe main constructionThe main constructionDetermining “latest” value for memSimulating snapshotsThe codeA code bugThe code, continuedCorrectness proofCorrect emulation of PSimulation relation proofBG for read/write memoryRecap: [BGLR]A Non-Boosting Result [Attie, Guerraoui, Kouznetsov, Lynch, Rajsbaum] Non-boosting resultf-resilient atomic objectsConcurrent invocationsSystem ModelBoosting Impossibility ResultA DeciderCase 1: Common process PiCase 2: Common f-resilient service SkCase 2: Common f-resilient service Sk, cont’dCase 3: Common register object SrRecap: [AGKLR]In contrast…Where are we? Next time…6.852: Distributed AlgorithmsFall, 2009Class 22Today’s plan• More on wait-free computability.• Wait-free vs. f-fault-tolerant computability• Reading: – [Borowsky, Gafni, Lynch, Rajsbaum]– [Attiya, Welch, Section 5.3.2]– [Attie, Guerraoui, Kouznetsov, Lynch, Rajsbaum]– [Chandra, Hadzilacos, Jayanti, Toueg]•Next time:– Shared-memory multiprocessor computation– Techniques for implementing concurrent objects:− Coarse-grained mutual exclusion− Locking techniques− Lock-free algorithmsz Reading:− [Herlihy, Shavit] Chapter 9But actually:• Next time:– Shared memory vs. networks– Consensus in asynchronous networks– Reading: • Chapter 17 of [Lynch book]• [ Lamport ] The Part-Time Parliament (Paxos)More on wait-free computability1. n-process consensus objects + registers can’t implement (n+1)-process consensus objects [Jayanti, Toueg].2. Irreducibility theorem [Chandra, Hadzilacos, Jayanti, Toueg].Consensus objects• Theorem: n-process consensus objects + registers can’t implement (n+1)-process consensus objects.• Proof: – Assume they can.– Can find a decider: bivalent, any step produces univalence.– At least one is 0-valent, one 1-valent.– Let P0= processes that produce 0-valence, P1= processes that produce 1-valence.– Consider any i0in P0, i1 in P1. – They must access the same object.• Else commutativity yields a contradiction.– Must be a consensus object.• If it’s a register, get [Loui, Abu-Amara] contradiction.– By considering all i0in P0, i1 in P1, can conclude all n+1 processes must access the same consensus object.– But it’s just an n-process consensus object, contradiction.α1n+12bivalentunivalentIrreducibility Theorem• [Chandra, Hadzilacos, Jayanti, Toueg]• Theorem: For every n ≥ 2 and every set S of types:– If there is a wait-free implementation of an n-process consensus object from (n-1)-process consensus objects, objects of types in S plus registers, – Then there is a wait-free implementation of n-process consensus from just objects of types in S plus registers.• That is, the (n-1)-process consensus objects don’t contribute anything!•Proof:An interesting series of constructions, rather complicated, LTTR.Open question• Can wait-free 2-process consensus objects plus registers be used to implement a wait-free 3-process queue? (Exercise?)Wait-free computability vs. f-fault-tolerant computabilityWait-free computability vs. f-fault-tolerant computability• We’ve been considering computability (of atomic objects) when any number of processes can fail (wait-free).• Now consider a bounded number, f, of failures.• [Borowsky, Gafni, et al.] transformation converts any n-process, f-fault-tolerant distributed shared r/w memory algorithm to an (f+1)-process f-fault-tolerant (wait-free) shared r/w memory algorithm, that solves a “closely related problem”.• Can derive wait-free algorithms from f-fault-tolerant algorithms.• Not obvious: – E.g., perhaps some shared-memory algorithm depends on having a majority of nonfaulty processes. – This says (in a sense) that this can’t happen.• Can infer impossibility results for f-FT shared-memory model from impossibility for wait-free shared-memory model.– E.g., impossibility for 2-process wait-free consensus [Herlihy] implies impossibility for 1-FT n-process consensus [Loui, Abu-Amara].Another consequence: k-consensus• Theorem: k-consensus is unsolvable for k+1 processes, with wait-free termination.– Proved by three teams:• [Borowsky, Gafni], [Herlihy, Shavit], [Saks, Zaharoglu]• Godel Prize•[BG]transformation implies impossibility for n-process k-consensus with k failures, n ≥ k+1.BG simulation• Citations:– Original ideas presented informally: [Borowsky, Gafni STOC 93]– More complete, more formal: [B, G, Lynch, Rajsbaum]What is a “Problem”?• Herlihy: – Problem = variable type– Studies wait-free algorithms that implement an atomic object of a given type.– Problems involve ongoing interactions.•BG:– All problems are one-shot:• Inputs arrive on some ports, at most one per port.• Outputs produced on some of those ports, at most one per port.– Problem = decision problem for n processes = set of pairs (I,O), where:• I and O are n-vectors over an underlying value domain V, and• Each I is paired with at least one O.• Example: k-consensus– I = O = all vectors over V– (I,O) ∈ D if and only if:• Every value in O appears somewhere in I, and• At most k distinct values appear in O.– Consensus: Special case of k-consensus for k = 1.Solving a Problem• An n-process shared-variable system solves an n-decision problem D, tolerating f failures, if all its executions satisfy:– Well-formedness: Produces answers only on ports where inputs are received, no more than once each.– Correct answers: If inputs occur on all ports, forming a vector I, then the outputs that are produced could be completed to a vector O such that (I,O) ∈ D.– f-failure termination: If inputs occur on all ports and at most f stop events occur, then an output occurs on each nonfailing port.• Same style as our earlier