Unformatted text preview:

6.852: Distributed Algorithms Spring, 2008Today’s planAsynchronous Shared-Memory systemsAsynch Shared-Memory systemsTopicsBasic ASM Model, Version 1Basic ASM Model, Version 2Basic ASM ModelThe Mutual Exclusion ProblemSlide 10Slide 11Slide 12One more assumption…6.852: Distributed AlgorithmsSpring, 2008Class 13Today’s plan•The asynchronous shared-memory model•The mutual exclusion problem•Dijkstra’s algorithm•Peterson’s algorithms•Lamport’s Bakery algorithm•Reading: Chapter 9, 10.1-10.5, 10.7•Next: Sections 10.6-10.8Asynchronous Shared-Memory systems•We’ve covered basics of non-fault-tolerant asynchronous network algorithms:–How to model them.–Basic asynchronous network protocols---broadcast, spanning trees, leader election,…–Synchronizers (running synchronous algorithms in asynch networks)–Logical time–Global snapshots•Now consider asynchronous shared-memory systems:p1p2pnx2x1•Processes, interacting via shared objects, possibly subject to some access constraints.•Shared objects are typed, e.g.:–Read/write (weak)–Read-modify-write, compare-and-swap (strong)–Queues, stacks, others (in between)Asynch Shared-Memory systems•Theory of ASM systems has much in common with theory of asynchronous networks:–Similar algorithms and impossibility results.–Even with failures.–Transformations from ASM model to asynch network model allow ASM algorithms to run in asynchronous networks.•“Distributed shared memory”.•Historically, ASM models were studied first: –Arose in study of early operating systems, in which several processes can run on a single processor, sharing memory, with possibly-arbitrary interleavings of steps.•Currently, ASM models apply to multiprocessor shared-memory systems, in which several processes can run on separate processors and share memory.Topics•Define the basic system model, without failures.•Use it to study basic problems: –Mutual exclusion.–Other resource-allocation problems.•Introduce process failures into the model.•Use model with failures to study basic problems:–Distributed consensus–Implementing atomic objects: •Atomic snapshot objects•Atomic read/write registers•Wait-free and fault-tolerant computability theory•Modern shared-memory multiprocessors:–Practical issues–Algorithms–Transactional memoryBasic ASM Model, Version 1 •Processes + objects, modeled as automata.•Arrows:–Represent invocations and responses for operations on the objects.–Modeled as input and output actions.•Fine-granularity model, can describe:–Gap between invocation and response.–Concurrent (overlapping) operations:•Object could reorder.•Could allow them to run concurrently, interfering with each other.•We’ll begin with a simpler, coarser model:–Object runs ops in invocation order, one at a time.–In fact, collapse each operation into a single step.•Return to the finer model later.p1p2pnx2x1invoke(read)respond(v)p1x1invoke(write,v)respond()p1x1Basic ASM Model, Version 2•One big shared memory system automaton A.•External actions at process “ports”.•Each process i has:–A set statesi of states.–A subset starti,of start states. •Each variable x has:–A set valuesx of values it can take on.–A subset initialx of initial values.p1p2pnx1x2A•Automaton A:–States: State for each process, a value for each variable.–Start: Start states, initial values.–Actions: Each action associated with one process, and some also with a single shared variable.–Input/output actions: At the external boundary.–Transitions: Correspond to local process steps and variable accesses.•Action enabling, which variable is accessed, depend only on process state. •Changes to variable and process state depend also on variable value.•Must respect the type of the variable.–Tasks: One or more per process (threads).Basic ASM Model•Execution of A:–As specified by general definitions of executions, fair executions for I/O automata.–By fairness definition, each task gets infinitely many chances to take steps.–Model environment as a separate automaton, to express restrictions on environment behavior.p1p2pnx1x2A•Commonly-used variable types:–Read/write registers: Most basic primitive.•Allows access using separate read and write operations.–Read-modify-write: More powerful primitive:•Atomically, read variable, do local computation, write to variable.–Compare-and-swap, fetch-and-add, queues, stacks, etc.•Different results hold for different variable types.The Mutual Exclusion Problem•Share one resource among n user processes, U1, U2,…,Un.–E.g., printer, portion of a database.•Ui has four “regions”.–Subsets of its states, described by portions of its code.–C critical; R remainder; T trying; E exit•Cycle: •Architecture:–Uis and A are IOAs, compose.R T C Ep1p2pnx1x2AU1U2UnProtocols for obtaining and relinquishing the resourceThe Mutual Exclusion Problem•Actions at user interface:–Connect Ui to Pi–pi is Ui’s “agent”•Correctness conditions:–Well-formedness (Safety):•System also obeys cyclic discipline.•E.g., doesn’t grant resource when it wasn’t requested.–Mutual exclusion (Safety):•System never grants to > 1 user simultaneously.•Trace safety property.•Or, there’s no reachable system state in which >1 user is in C at once.–Progress (Liveness):•From any point in a fair execution:–If some user is in T and no user is in C then at some later point, some user enters C.–If some user is in E then at some later point, some user enters R.p1p2pnx1x2AU1U2UnpiUitryicritiexitiremiThe Mutual Exclusion Problem•Well-formedness (Safety):–System obeys cyclic discipline.•Mutual exclusion (Safety):–System never grants to > 1 user.•Progress (Liveness):–From any point in a fair execution:•If some user is in T and no user is in C then at some later point, some user enters C.•If some user is in E then at some later point, some user enters R.p1p2pnx1x2AU1U2Un•Conditions on the system automaton A, not the users.–System determines if/when users enter C and R.–Users determine if/when users enter T and E.–We don’t state any requirements on the users, but assume that users respect well-formedness.The Mutual Exclusion Problem•Well-formedness (Safety):•Mutual exclusion (Safety):•Progress (Liveness):–From any point in a fair execution:•If some user is in T and no user is in C then at


View Full Document

MIT 6 852 - Distributed Algorithms

Download Distributed Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Distributed Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Distributed Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?