6 852 Distributed Algorithms Fall 2009 Class 14 Today s plan Mutual exclusion with read write memory Lamport s Bakery Algorithm Burns algorithm Lower bound on the number of registers Mutual exclusion with read modify write operations Reading Sections 10 6 10 8 10 9 Next Lecture by Victor Luchangco Sun Practical mutual exclusion algorithms Generalized resource allocation and exclusion problems Reading Herlihy Shavit book Chapter 7 Mellor Crummey and Scott paper Dijkstra prize winner Optional Magnussen Landin Hagersten paper Distributed Algorithms Chapter 11 Last time z Mutual exclusion with read write memory Dijkstra s algorithm Mutual exclusion progress Peterson s algorithms Mutual exclusion progress lockout freedom Lamport s Bakery algorithm didn t get to this Mutual exclusion progress lockout freedom No multi writer variables Lamport s Bakery Algorithm Like taking tickets in a bakery Nice features Uses only single writer multi reader registers Extends to even weaker registers in which operations have durations and a read that overlaps a write receives an arbitrary response Guarantees lockout freedom in fact almost FIFO behavior But Registers are unbounded size Algorithm can be simulated using bounded registers but not easily uses bounded concurrent timestamps Shared variables For each process i choosing i a Boolean written by i read by all initially 0 number i a natural number written by i read by all initially 0 Bakery Algorithm First part up to choosing i 0 the Doorway D Process i chooses a number number greater than all the numbers it reads for the other processes writes this in number i While doing this keeps choosing i 1 Two processes could choose the same number unlike real bakery Break ties with process ids Second part Wait to see that no others are choosing and no one else has a smaller number That is wait to see that your ticket is the smallest Never go back to the beginning of this part just proceed step by step waiting when necessary Code Shared variables for every i 1 n choosing i 0 1 initially 0 writable by i readable by all j z i number i a natural number initially 0 writable by i readable by j z i tryi choosing i 1 number i 1 maxj z i number j choosing i 0 for j z i do waitfor choosing j 0 waitfor number j 0 or number i i number j j criti exiti number i 0 remi Correctness Mutual exclusion Key invariant If process i is in C and process j z i is in T D C Trying region after doorway or critical region then number i i number j j Proof Could prove by induction Instead give argument based on events in executions This argument extends to weaker registers with concurrent accesses Correctness Mutual exclusion Invariant If i is in C and j z i is in T D C then number i i number j j Proof Consider a point where i is in C and j z i is in T D C Then before i entered C it must have read choosing j 0 event S S i reads choosing j 0 i in C j in T D C Case 1 j sets choosing j 1 starts choosing after S Then number i is set before j starts choosing So j sees the correct number i and chooses something bigger Case 2 j sets choosing j 0 finishes choosing before S Then when i reads number j in its second waitfor loop it gets the correct number j Since i decides to enter C anyway it must have seen number i i number j j Correctness Mutual exclusion Invariant If i is in C and j z i is in T D C then number i i number j j Proof of mutual exclusion Apply invariant both ways Contradictory requirements Liveness Conditions Progress By contradiction If not eventually region changes stop leaving everyone in T or R and at least one process in T Everyone in T eventually finishes choosing Then nothing blocks the smallest number index process from entering C Lockout freedom Consider any i that enters T Eventually it finishes the doorway Thereafter any newly entering process picks a bigger number Progress implies that processes continue to enter C as long as i is still in T In fact this must happen infinitely many times But those with bigger numbers can t get past i contradiction FIFO Condition Not really FIFO oT vs oC but almost FIFO after the doorway if j leaves D before i oT then j oC before i oC But the doorway is an artifact of this algorithm so this isn t a meaningful way to evaluate the algorithm Maybe say there exists a doorway such that But then we could take D to be the entire trying region making the property trivial To make the property nontrivial Require D to be wait free a process is guaranteed to complete D it if it keeps taking steps regardless of what other processes do D in the Bakery Algorithm is wait free The algorithm is FIFO after a wait free doorway Impact of Bakery Algorithm Originated important ideas Wait freedom Fundamental notion for theory of fault tolerant asynchronous distributed algorithms Weakly coherent memories Beginning of formal study definitions and some algorithmic strategies for coping with them Space and memory considerations z All mutual exclusion algorithms use more than n variables Bakery algorithm could use just n variables Why z All but Bakery use multi writer variables These z can be expensive to implement Bakery uses infinite size variables Difficult but possible to adapt to use finite size variables z Q Can we do better Burns Algorithm Burns algorithm Uses just n single writer Boolean read write variables z Simple z Guarantees safety mutual exclusion and progress z But not lockout freedom Code Shared variables for every i 1 n flag i 0 1 initially 0 writable by i readable by all j z i Process i tryi L flag i 0 for j 1 i 1 do if flag j 1 then go to L flag i 1 for j 1 i 1 do if flag j 1 then go to L M for j i 1 n do if flag j 1 then go to M criti exiti flag i 0 remi That is Each process goes through 3 loops sequentially 1 Check flags of processes with smaller indices 2 Check flags of processes with smaller indices 3 Check flags of processes with larger indices If it passes all tests o C Otherwise drops back L M Correctness of Burns algorithm Mutual exclusion progress Mutual exclusion Like the proof for Dijkstra s algorithm but now with flags set to 1 rather than 2 If processes i and j are ever in C simultaneously both must have set their flags 1 Assume WLOG that process i sets flag i 1 for the last time first Keeps flag i 1 until process i leaves C After flag i 1 must have flag j 1 then j must see flag i 0 before j o C Impossible Progress for Burns algorithm z z z …