Wait-Free Consensus
CPSC 661
Fall 2003
Supervised by:
Presented by:
Lisa Higham
Wei Wei Zheng
Nuha Kamaluddeen
• 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
• 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
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
R/W registers
Test&set, swap, fetch&add, queue, stack
2n - 2
n-register assignment
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
• 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
• Deterministic Wait-Free: Any process can
complete any operation in an finite
number of steps of that process
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
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.
M. Herlihy. Wait-Free Synchronization. ACM Transactions on
Programming Languages and Systems, 13(1): 124-149. January
M. Herlihy. Randomized Wait-Free Concurrent Objects. In
proceedings of the 10th annual ACM Symposium on Principles of
Distributed Computing, August 1991, Montreal Canada

Wait-Free Consensus - University of Calgary