Wait-Free Consensus CPSC 661 Fall 2003 Supervised by: Presented by: Lisa Higham Wei Wei Zheng Nuha Kamaluddeen Outline • Deterministic Wait-Free • Consensus Problem • FLP vs. Herlihy • Impossibility and Universality • Randomized Wait-Free Deterministic Wait-Free • Wait-Free Implementation is the one which guarantees that any process can complete any operation in a finite number of steps of that process • Given two concurrent objects X and Y • Q: Does there exist a wait-free implementation of X by Y? • FLP and Herlihy’s papers answered this question Consensus Problem • A system of n processes that communicate through m shared objects – Each process starts with an input value from domain D – Communicates with one another by applying operations to the shared objects – Eventually agree on a common input value and halt Consensus Problem • Requirements: – Agreement: all processes decide on one common value if they do decide – Validity: the common decision value is the input of some process – Wait-Freedom: each process decides after a finite number of steps Consensus Number • Consensus Number for an object X is the largest n for which X solves consensus problem for n processes • If no largest n exists, then the consensus number is said to be infinite FLP vs. Herlihy • FLP answered the question for a specific object, i.e., R/W register. • FLP provided a stronger result for this special case: no implementation of consensus problem of n>=2 processes using R/W registers, even for at most 1 stopping faulty process, and even for binary inputs • Herlihy gave a more generalized answer: Impossibility and Universality Hierarchy for waitfree implementation of any type of object Impossibility and Universality Hierarchy Object Consensus Number 1 R/W registers 2 Test&set, swap, fetch&add, queue, stack 2n - 2 n-register assignment Infinity Memory-to-memory move and swap, augmented queue, compare&swap, fetch&cons, sticky byte Impossibility and Universality • Impossibility – It is impossible to construct a wait-free implementation of an object with consensus number n from any number of objects with a lower consensus number Impossibility and Universality • Universality: an object is universal in a system of n (or fewer) processes if it can implement any object of consensus number n (i.e., if it can solve the consensus problem for up to n processes) • Any object with consensus number n is universal in a system of n (or fewer) processes Why Is It Important • Research done before was focusing on constructing complex objects from atomic R/W registers • Atomic registers have few applications in constructing waitfree implementation of more complex data structure, e.g., queue and test&set • Turning Points: – Pay attention to other primitives: stronger than R/W registers – Give up wait-free – Use randomized wait-free Randomized Wait-Free Randomized • Deterministic Wait-Free: Any process can complete any operation in an finite number of steps of that process expected Importance of Randomization • We can construct a randomized wait-free implementation of Read-Modify-Write by atomic R/W operations • Read-Modify-Write is universal • So, atomic R/W operation is universal • Herlihy’s hierarchy collapses to 1 level using randomization References 1. M. Fischer, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of ACM, Vol. 32, No. 2, April 1985, pp. 374-382. 2. M. Herlihy. Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems, 13(1): 124-149. January 1991. 3. M. Herlihy. Randomized Wait-Free Concurrent Objects. In proceedings of the 10th annual ACM Symposium on Principles of Distributed Computing, August 1991, Montreal Canada Questions?