6.852: Distributed Algorithms Fall, 2009 Class 17Today’s plan • Atomic objects: – Basic definitions – Canonical atomic objects – Atomic objects vs. shared variables • Reading: Sections 13.1-13.2 • Next time: – More atomic objects: • Atomic snapshots • Atomic read/write registers – Reading: Sections 13.3-13.4Shared memory model z Single I/O automaton with processes and variables “inside”. z Separation expressed by locality restrictions on the actions and transitions. z Processes and variables aren’t separate automata. z Doesn’t exploit I/O automaton (de)composition. z Can’t talk about implementing shared variables with lower-level distributed algorithms. z Q: Could we model each process and variable as a separate I/O automaton?  Split operations on variables into separate invocation and response actions. p1 p2 pn x1 x2 A  But we still want an invocation/response to “look like” an instantaneous access. z Define atomic objects:  Interface has invocation inputs and response outputs.  Invocation/response behavior “looks like” that of an instantaneous-access shared variable. z AKA linearizable objects [Herlihy, Wing]Atomic objects Wait-free termination resp f-failure termination z Interface has invocation inputs and response outputs. AtomicObjectrespinv z Invocation/response behavior “looks like” that of an respinstantaneous-access shared variable. inv z Atomic object of a given type is similar to an ordinary shared variable of that type, but it allows concurrent accesses by different processes. z Still looks “as if” operations occur one at a time, sequentially, in some order consistent with order of invocations and responses. inv z Fault-tolerance conditions, as for consensus: z z z Separating invocations and responses allows us to consider lower-levelimplementations of these objects. z Shared-memory algorithms, or distributed network algorithms. z For shared memory algorithms, can develop algorithms hierarchically, usingseveral levels. z Atomic objects are important building blocks for multiprocessor systems anddistributed systems.Replacing variables with atomic objects • Now processes and objects are all I/O automata, combinedusing ordinary automata composition. • Interactions: – Processes access atomic objects via invocations, get responses. – Invocations are outputs of processes, inputs of objects. – Responses are outputs of objects, inputs of processes. – May be a gap between invocation and response. p1 p2 pn x1 x2 A U1 U2 Un p1 p2 pn x1 x2 A U1 U2 UnReplacing variables with atomic objects • “Locality” is now automatic from I/O automata composition. • More complicated than shared variables: – More actions (invocations/responses instead of entire accesses). – Algorithms have more steps, more bookkeeping. – More stuff to reason about. • More realistic system model. p1 p2 pn x1 x2 A U1 U2 Un p1 p2 pn x1 x2 A U1 U2 UnAtomic objects z Replace variables with atomic objects can decompose system in different ways z what a process is depends on your point of view z can compose objects into larger objects p1 p2 pn x1 x2 A U1 U2 Un p1 p2 pn x1 x2 U1 U2 Unbut we need some restrictions to get “equivalance” handling failures, in particular, is tricky z delay for later in lecture p1 p2 pn x1 x2 A U1 U2 Un p1 p2 pn x1 x2 U1 U2 UnAtomic objects: Basic definitionsAtomic object definitions z Variable type: (V, v0, invs, resps, f)  V: Set of values  v0: Initial value  invs: Set of invocations  resps: Set of responses  f: invs × V o resps × V  Describes responses to an invocation and associated changes tothe variable. z AKA Sequential specification [Herlihy], State machine [Lamport] z Execution: v0, a1, b1, v1, a2, b2, v2, a3, b3, v3, a4, b4, v4,...  vi is value; ai is invocation; bi is response  Ends with value (if finite).  (bi, vi) = f(ai, vi-1) for i > 0. z Trace: a1, b1, a2, b2, a3, b3, a4, b4,... (i.e., just invocations andresponses, but no variable values)Atomic objects Atomic Object A inv resp resp inv resp inv • Atomic object A of a given type is an I/Oautomaton with a particular kind ofinterface, satisfying some conditions: – Well-formedness – Atomicity – Liveness (termination) • External interface:  Assume “ports” 1, 2, ..., n (one for each process). – May restrict so that some invocations are allowed on some of the ports, not all. – Also allow stop inputs on all ports, as before. • Compose with users Ui, assumed topreserve well-formedness (alternatinginvocations and responses at each port,starting with invocation).Conditions satisfied by A • Preserves well-formedness (alternating invocations andresponses at each port, starting with invocation). • Atomicity: – First define when a well-formed sequence E of invocations and responses (at all ports) is atomic. – Then A satisfies atomicity iff all well-formed executions of A u U, where U = 3 Ui (for any users) have atomic traces. • First suppose that all invocations have matching responses (that is, the sequence E is complete). • Then we say E is atomic provided that it’s possible to insert a serialization point (dummy event) somewhere betweeneach invocation and matching response, such that, if all theinvs and resps are moved to their serialization points, the result is a trace of the (serial) variable type.Atomicity for complete sequences • Suppose E is a complete well-formed sequence of invocations and responses. Then E is atomic provided that one can insert a serialization pointbetween each invocation and matching response, such that, if all theinvs and resps are moved to their serialization points, the result is a trace of the (serial) variable type. • Examples: Initial value 0. * write(8) ack write(8) ack read 0 * * read 8 * • read, 0, write(8), ack is correct for serial specification. • write(8), ack, read, 8 is also correct.Alternative definition [Herlihy] • Suppose E is a complete well-formed sequence of invocations and responses. Then E is atomic provided that it can be reordered to a trace of the variable type, while preserving: – The order of events at each process, and – The order of any response and following invocation (anywhere). • Equivalent.Complication: Incomplete operations •Q: What about sequences E containing some incomplete operations? Which ops