```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
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
atomic R/W operations
• 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?
```