6.852: Distributed Algorithms Fall, 2009Today’s planGeneralized resource allocationResource specificationsResource allocation problem, for a given exclusion spec EDining Philosophers Dining Philosophers Asynchronous shared-memory systems with failuresAsynchronous shared-memory systems with failuresConsensus in asynchronous shared-memory systems with failuresConsensus in Asynchronous Shared-Memory SystemsConsequences of impossibility resultsArchitectureProblem requirements 1Problem requirements 2: Fault-toleranceImpossibility of agreementRestrictions (WLOG)TerminologyUnivalence and BivalenceExhaustive classificationBivalent initializationBivalent initializationImpossibility for wait-free terminationImpossibility for wait-free terminationImpossibility for wait-free terminationImpossibility for wait-free terminationCase 1: i’s step is a read Case 2: j’s step is a read Case 3: Writes to different shared variables Case 4: Writes to the same shared variable x. Impossibility for wait-free terminationImpossibility for 1-failure teminationImpossibility for 1-failure teminationLemma 4  Main TheoremProof of Lemma 4Proof of Lemma 4New “Decider”Case 1: i’s step is a read Case 2: j’s step is a read Case 3: Writes to different shared variables Case 4: Writes to the same shared variable x. Impossibility for 1-failure terminationShared memory vs. networksSignificance of FLP impossibility result Strengthening the assumptionsWeakening the requirementsExtension to k-consensusImportance of read/write data typeNext time…6.852: Distributed AlgorithmsFall, 2009Class 16Today’s plan• Generalized resource allocation• Asynchronous shared-memory systems with failures.• Consensus in asynchronous shared-memory systems.• Impossibility of consensus [Fischer, Lynch, Paterson]• Reading: Chapter 11, Chapter 12• Next: Chapter 13Generalized resource allocationz Mutual exclusion: Problem of allocating a single non-sharable resource.z Can generalize to more resources, some sharing.z Exclusion specification E (for a given set of users):z Any collection of sets of users, closed under superset.z Expresses which users are incompatible, can’t coexist in the critical section.z Example: k-exclusion (any k users are ok, but not k+1)E = { E : |E| > k }z Example: Reader-writer locks z Relies on classification of users as readers vs. writers.E = { E : |E| > 1 and E contains a writer }z Example: Dining Philosophers [Dijkstra]E = { E : E includes a pair of neighbors }Resource specifications• Some exclusion specs can be described conveniently in terms of requirements for concrete resources.• Resource specification: Different users need different subsets of resources– Can't share: Users with intersecting sets exclude each other.z Example: Dining PhilosophersE = { E : E includes a pair of neighbors }– Forks (resources) between adjacent philosophers; each needs bothadjacent forks in order to eat.– Only one can hold a particular fork at a time, so adjacent philosophers must exclude each other.• Not every exclusion problem can be expressed in this way.– E.g., k-exclusion cannot.Resource allocation problem, for a given exclusion spec E• Same shared-memory architecture as for mutual exclusion (processes and shared variables, no buses, no caches).• Well-formedness: As before.• Exclusion: No reachable state in which the set of users in C is a set in E.• Progress: As before.• Lockout-freedom: As before.• But these don’t capture concurrency requirements.• Any lockout-free mutual exclusion algorithm also satisfies E (provided that E doesn’t contain any singleton sets).• Can add concurrency conditions, e.g.:– Independent progress: If i ∈T and every j that could conflict with i remains in R, then eventually i → C. – Time bound: Obtain better bounds from i → T to i → C, even in the presence of conflicts, than we get for mutual exclusion.Dining Philosophers • Dijkstra’s paper posed the problem, gave a solution using strong shared-memory model.– Globally-shared variables, atomic access to all of shared memory.– Not very distributed.• More distributed version: Assume the only shared variables are on the edges between adjacent philosophers.– Correspond to forks.– Use RMW shared variables.• Impossibility result: If all processes are identical and refer to forks by local names “left” and “right”, and all shared variables have the same initial values, then we can’t guarantee DP exclusion + progress.•Proof:Show we can’t break symmetry: – Consider subset of executions that work in synchronous rounds, prove by induction on rounds that symmetry is preserved.– Then by progress, someone → C.– So all do, violating DP exclusion.Dining Philosophers • Example: Simple symmetric algorithm where all wait for R fork first, then L fork. – Guarantees DP exclusion, because processes wait for both forks.– But progress fails---all might get R, then deadlock.• So we need something to break symmetry.• Solutions:– Number forks around the table, pick up smaller numbered fork first.– Right/left algorithm (Burns):• Classify processes as R or L (need at least one of each).• R processes pick up right fork first, L processes pick up left fork first.• Yields DP exclusion, progress, lockout freedom, independent progress, and good time bound (constant, for alternating R and L).z Generalize to solve any resource problem− Nodes represent resources.− Edge between resources if some user needs both.− Color graph; order colors.− All processes acquire resources in order of colors.Asynchronous shared-memory systems with failuresAsynchronous shared-memory systems with failures• Process stopping failures.• Architecture as for mutual exclusion.– Processes + shared variables, one system automaton.–Users•Add stopiinputs.– Effect is to disable all future non-input actions of process i.• Fair executions:– Every process that doesn’t fail gets infinitely many turns to perform locally-controlled steps.– Just ordinary fairness---stop means that nothing further is enabled.– Users also get turns.p1p2pnx1x2AU1U2Unstop1stop2stopnConsensus in asynchronous shared-memory systems with failuresConsensus in Asynchronous Shared-Memory Systems• Recall: Consensus in synchronous networks.– Algorithms for stopping failures:• FloodSet, FloodMin,