Wait- Free

Please download to get full document.

View again

of 12
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Documents

Published:

Views: 4 | Pages: 12

Extension: PDF | Download: 0

Share
Related documents
Description
disributed computing
Tags
Transcript
  1 CS586 -Panagiota Fatourou1 Section 7Wait-Free Simulations of Arbitrary Objects CS586 -Panagiota Fatourou2 Wait-Free Simulations of Arbitrary Shared Objects  The consensus problem cannot be solved using only read/writeregisters.  Most modern multiprocessors provide some set of ‘’stronger’’hardware primitive for coordination, like LL/SC or Compare&Swap.  We investigate the following question:“Given two types of (linearizable) shared objects, X and Y, is there a wait-free simulation of object type Y using only objects of type X and read/write registers?”  We will first answer this question for the weaker termination property called non-blocking (or lock-freedom):“Lock-freedom states that there is a finite execution fragment starting at any point of an admissible execution in which some high-level operations are pending, at which a process completes one of the pending operations. ”  Lock-freedom is a weaker property than wait-freedom which statesthat eventuallyall processes shouldcomplete their operations.  Lock-freedom allows starvation to occur!  The distinction between wait-free and lock-free algorithms is similar to the distinction between no-lockout and no-deadlock algorithms for mutual exclusion.  2 CS586 -Panagiota Fatourou3 Example: A FIFO Queue ãThe operations supported by a FIFO queue are: –[enq(Q,x), ack(Q)],–[deq(Q), return(Q,x)], where x can be any value that can be stored in the queue (deq(Q) returns ⊥ if the queue is empty). Theorem1 ãAlgorithm 1 solves consensus for two processes. 1: CS586 -Panagiota Fatourou4 Example: A FIFO Queue Theorem 2 ãThere is no wait-free simulation of a FIFO queue with read/write objects, for any number of processes. Proof: ã If there was a wait-free simulation of FIFO queues with read/write objects, then there would be a wait-free consensus algorithm, for two processes, using only read/write objects. ã This is a contradiction to the FLP result!!!Theorem 3 ãThere is no n-process, wait-free consensus algorithm using only FIFO queues and read/write objects, if n ≥ 3. Proof: Using valence arguments as in previous section. Left as an exercise!!!  3 CS586 -Panagiota Fatourou5 The strong Compare&SwapPrimitive! Theorem 4 ãAlgorithm 2 solves consensus for any number of processes using a single Compare&Swapobject. value  Compare&Swap (X: memory address  ; old, new: value  ) {previous = X;if (previous == old) then X = new;return previous;} 2: CS586 -Panagiota Fatourou6 The Wait-Free Hierarchy ãAtomic objects can be categorized according to a criterion which is based on their ability to support a consensus algorithm for a certain number of processes. ãObject type X solves wait-free n-processes consensus if there exists an asynchronous consensus algorithm for n processes using only shared objects of type X and read/write objects. ãThe consensus numberof object type X is n, denoted CN(X) = n, if n is the largest value for which X solves wait-free n-processes consensus. The consensus number is infinity if X solves wait-free n-processes consenusfor every n.  The consensus number of any object X is at least 1, because any object trivially solves wait-free one-process consensus.  4 CS586 -Panagiota Fatourou7 The Wait-Free Hierarchy  For each object typeΧwhich is the smallest value thatCN(X)can have?   The CN of aread/writeregister is1.  The CNof the following atomic shared objects is2: test&set, swap, fetch&add, stacks, queues.  The CN of aCompare&Swapregister is  ∞ .  There exists a hierarchyof object types based on theirCN.  It has been proved that there are object types with CN= m, for each value of m>0. CS586 -Panagiota Fatourou8 The Wait-Free Hierarchy Theorem 5 ãIf CN(X) = m and CN(Y) = n > m, then there is no wait-free simulation of Y with X and read/write objects in a system with more than m processes. Proof: Assume, by the way of contradiction, that there is a wait-free implementation of Y from objects of type X and read/write registers in a system with k > m processes. ãDenote l = min{k,n}. Note that l > m.ãWe argue that there exists a wait-free l-processes consensus algorithm using objects of type X and read/write objects.ãSince l ≤n, there exists a wait-free l-processes consensus algorithm, A, using objects of type Y and read/write objects.ãWe can obtain another algorithm A’by replacing each type Y object with a wait-free simulation of it using objects of type X and read/write registers. ãA’is a wait-free l-processes consensus algorithm using objects of type X and read/write objects ⇒ CN(X) ≥ l > m. This is a contradiction!
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks