6.852: Distributed AlgorithmsSpring, 2008Class 19Today’s plan•Wait-free synchronization.•The wait-free consensus hierarchy•Universality of consensus•Reading:–[Herlihy, Wait-free synchronization] (Another Dijkstra Prize paper)–[Attiya, Welch, Chapter 15]Overview•General goal: –Classification of atomic object types: Which types of objects can be used to implement which other types, for which numbers of processes and failures. –A theory of relative computability, for objects in distributed systems.•Follow Herlihy’s approach.•Considers wait-free termination only (n-1 failures).•Object types:–Primitives used in multiprocessor memories:•Test-and-set, fetch-and-add, compare-and-swap–Standard programming data types:•Counters, queues, stacks–Consensus, k-consensus•Hierarchy of types, with:–Read/write registers at the bottom, level 1–Consensus (viewed as an atomic object) at the top, level ∞–Others in between.•Universality result: Can use consensus for n processes to implement (wait-free) any object for n processes.Herlihy’s Hierarchy•Defines hierarchy in terms of:–How many processes can solve consensus using only objects of the given type, plus registers (thrown in for free).•Shows that no object type at one level of the hierarchy can implement objects at higher levels.•Shows:–Read/write registers are at level 1.–Stacks, queues, fetch-and-add, test-and-set are at level 2.–Consensus, compare-and-swap are at “level ∞”.•Hierarchy has a few limitations:–All of the interesting types are at level 1, 2 or ∞.–Gives no information about relative computability of objects at the same level.–Lacks some basic “robustness” properties.•Yields some interesting classification results.•More work is needed.The Model•Based on I/O automata.–Herlihy claims he doesn’t need tasks, but we’ll use them to define fair executions, as usual.•Concurrent system:–Processes + atomic objects•Sequential specification = variable type•Use such a concurrent system to implement an atomic object, of a specified type.•Warning: Herlihy’s definition of implementation consider one object R, but results allow many objects (of one type).P1AmA1P2Pninvoke, respondConsensus as an atomic object•Define the consensus variable type (X, x0, invs, resps, δ):–Let V = consensus domain.–Define X = V ∪ { ⊥ }.–x0 = ⊥–invs = { init(v) | v ∈ V }–resps = { decide(v) | v ∈ V }–δ(init(v), ⊥) = (decide(v), v), for any v in V –δ(init(w), v) = (decide(v), v), for any v, w in V•First value provided in an init() operation is everyone’s decision.•Herlihy’s consensus object is simply a wait-free atomic object for the consensus variable type.•Lets him consider atomic objects everywhere:–For high-level objects being implemented, and–For low-level objects used in the implementations.•Usually treats low-level objects as shared variables (as we do).Herlihy’s consensus object vs. our consensus definition•Herlihy’s consensus atomic object is “almost the same” as our definition of consensus:–Satisfies well-formedness, agreement, strong validity (every decision is someone’s initial value).–Wait-free termination.•Every init() on a non-failing port eventually receives a decide() response.•Some (unimportant) differences:–Allows repeated operations on the same port; but all get the same value v.–Inputs needn’t arrive everywhere; equivalent requirement (Exercise 12.1)Binary vs. arbitrary consensus•Herlihy’s paper talks about “implementing consensus”, without specifying the domain.•Doesn’t matter:•Theorem: Let T be the consensus type with domain { 0,1 }, and T' the consensus type with any finite value domain V. Then there is a wait-free implementation of an n-process atomic object of type T' from n-process shared variables of type T and read/write registers.Algorithm•Shared variables:–Boolean consensus objects, cons(1),…,cons(k), where k is the length of a bit string representation for elements of V.–Registers init(1),…, init(n) over V ∪ { ⊥ }, where V is the consensus domain, initially all ⊥.•Process i:–Post your initial value in init(i), as a bit string.–Maintain a current preference, locally, initialized to init(i).–For l = 1 to k do:•Engage in binary consensus on cons(l), with l-order bit of your current preference as input.•If your bit loses, then:–read all init(j) registers to find some value whose first l-1 bits agree with your current preference, and whose l’th bit is the winning bit from cons(l). –Reset your preference to this init(j).–Return your final preference.Extension to infinite V•Theorem: Let T be the consensus type with domain { 0,1 }, T' the consensus type with any value domain V. Then there is a wait-free implementation of an n-process atomic object of type T' from n-process shared variables of type T and read/write registers.•Proof:–Similar algorithm.–Now reach consensus on index j, rather than value, for some active process (one that wrote init(j)). –Then return init(j).•Moral: When we talk about “solving consensus”, we needn’t specify V (unless we care about complexity).Consensus Numbers•Definition: The consensus number of a variable type T is the largest number n such that shared variables of type T and read/write registers can be used to implement an n-process wait-free atomic consensus object.•That is, T + registers solve n-process consensus.•Notes:–Registers are thrown in for free.–Convenient in writing algorithms.–OK because they are at the bottom of the hierarchy (consensus number 1).•Follows from [Loui, Abu-Amara]•Definition: If T + registers solve n-process consensus for every n, then we say that T has consensus number ∞.Consensus Numbers•Consensus numbers yield a way of showing that one variable type T cannot implement another variable type T', for certain numbers of processes.•Theorem 1: Suppose cons-number(T) = m, and cons-number(T') > m. Then there is no (wait-free) implementation of an atomic object of type T' for n > m processes, from shared variables of type T and registers. •Proof: –Enough to show for n = m+1.–By contradiction. Suppose there is an (m+1)-process implementation of an atomic object of type T' from T + registers.–Since cons-number(T') > m, there is an (m+1)-process consensus algorithm C using T' + registers.–Replace the