6.852: Distributed Algorithms Fall, 2009Today’s planShared memory vs. NetworksPaxosSimulating networks using shared-memory systemsSimulating networks using shared-memory systemsAlgorithmSome pseudocodeAn important corollaryAnother corollaryIs this counterintuitive?Simulating shared-memory systems using networksSimulating shared-memory in distributed networksNon-fault-tolerant simulation of shared memory in distributed networksShared memory in networksSingle-copy simulation More formally…More formally…More formally…Some issuesMulti-copy simulationMulti-copy simulation: Bad examplesMulti-copy simulationMajority-voting algorithmsMajority-voting algorithmsMajority-voting algorithmsSome issuesFault-tolerant simulation of shared memory in distributed networksFault-tolerant simulation of shared memory in distributed networks[ABD] Guarantees[ABD] algorithm[ABD] atomic object algorithmABD algorithmCorrectness of [ABD] atomic object algorithmCorrectness of [ABD] atomic object algorithmAtomicity, cont’d[ABD] Simulation [ABD] Simulation Corollaries Some issuesImpossibility of n/2-fault-toleranceImpossibility of n/2-fault-toleranceProof, cont’dAn implicationFault-Tolerant Agreement in Asynchronous Networks: The Paxos AlgorithmAgreement in asynchronous networksBest approachEventually stable approach: Some historyPaxos consensus protocolThe nondeterministic “safe” algorithm: BallotsThe safe algorithm: QuorumsSafe algorithm, centralized versionSafe algorithm, centralized versionSafe algorithm, centralized versionSafety propertiesModifying the ** condition for assigning ballot valuesSafe algorithm, distributed versionSafe algorithm, distributed versionEnsuring (***)Ensuring (***)Safe algorithm, distributed version, cont’dLivenessReplicated state machines (RSMs)Next time6.852: Distributed AlgorithmsFall, 2009Class 23Today’s plan• Shared memory vs. networks• Consensus in asynchronous networks• Reading: – Chapter 17 – [ Lamport ] The Part-Time Parliament (Paxos)• Next time:– Self-stabilization– [Dolev book], Chapter 2Shared memory vs. Networks• Simulating shared memory in distributed networks:– Popular method for simplifying distributed programming.– Distributed shared memory (DSM).– Easy if there are no failures.– Possible if n > 2f; impossible if n ≤ 2f.– [Attiya, Bar-Noy, Dolev] fault-tolerant algorithm• Simulating networks using shared memory:– Easier, because shared memory is “more powerful”.– Works for any number of failures.– Useful mainly for lower bounds, impossibility results.• Carry over impossibility results for shared memory model to network model• E.g., for fault-tolerant consensus.Paxos• A fault-tolerant consensus algorithm for distributed networks.• Can use it to implement a fault-tolerant replicated state machine (RSM) in a distributed network.• Generalizes Lamport’s timestamp-based non-fault-tolerant RSM algorithm.Simulating networks using shared-memory systemsp1p2pnx1x2AC2,1p1C1,2p2Simulating networks using shared-memory systems• Easy transformation from networks to shared-memory, because shared-memory model is more powerful:– Has reliable, instantaneously-accessible shared memory.– No arbitrary delays as in channels.• Transformation preserves fault-tolerance, even for f ≥ n/2.• Assume: – Asynchronous network system A, running on undirected graph network G.– Failures: stopievent disables Piand has no effect on channels.• Produce:– Asynchronous read/write shared-memory system B simulating A, in the same sense as for atomic objects:– For any execution α of the shared-memory system B × U, there is an execution α′ of the network system A × U such that:• α | U = α′ | U and•stopievents occur for the same i in α and α′.• If α is fair then α′ is also fair.Algorithm• Replace channel Ci,jwith a 1-writer, 1-reader shared variable x(i,j), writable by i, readable by j.•x(i,j)contains a queue of messages, initially empty.• Process i adds messages, never removes any.• Process i simulates automaton Pi, step by step.–To simulate send(m)i,j, process i adds m to end of x(i,j).• Does this using a write operation, by remembering what it wrote there earlier.– Meanwhile, process i keeps checking its incoming variables x(j,i),looking for new messages.• Does this by remembering what it saw there before.• When it finds a new message, process i handles it the same way Pi would handle it.Some pseudocodez State variables for process i− pstate : states(Pi)− sent(j) for each out-neighbor j: sequence of M, initially empty− rcvd(j), processed(j) for each in-neighbor j: seq of M, initially emptyz Transitions for i− Internal send(m,j)i:z pre: send(m)i,jenabled in pstateiz eff: append m to sent(j); x(i,j) := sent(j); update pstate as for send(m)i,j− Internal receive(m,j)Iz pre: true z eff: rcvd(j) := x(j,i);update pstate using messages in rcvd(j) - processed(j); processed(j) := rcvd(j)− All others: As for Pi, using pstate.An important corollary• Theorem: This simulation produces an asynchronous shared-memory system B simulating A, in the sense that, for any execution α of the shared-memory system B × U, there is an execution α′ of the network system A × U such that:• α | U = α′ | U.•stopIevents occur for the same i in α and α′.• If α is fair then α′ is also fair.z Corollary: Consensus is impossible in asynchronous networks, with 1 stopping failure [Fischer, Lynch, Paterson].z Proof: z If such an algorithm existed, we could simulate it in an asynchronous shared-memory system using the simulation just given.z This would yield a 1-fault-tolerant consensus algorithm for (1-writer 1-reader) read/write shared memory.z We already know this is impossible [Loui, Abu-Amara].Another corollaryz Corollary: Consensus is impossible in asynchronous broadcast systems, with 1 stopping failure [Fischer, Lynch, Paterson].z Asynchronous broadcast system: Process can put a message in all its outgoing channels in one step, and all are guaranteed to eventually be delivered.z Process cannot fail in the middle of a broadcast.z Proof: z If such an algorithm existed, we could simulate it in an asynchronous shared-memory system using a simple extension of the simulation above.z Extension uses 1-writer multi-reader shared variables to represent the broadcast channels.z This would yield a 1-fault-tolerant consensus algorithm