  The consensus number of an object is the maximum number of processes among
which binary consensus can be solved using any number of instances of the
object and read-write registers. Herlihy [6] showed in his seminal work that if
an object has a consensus number of n, then there is a universal construction
for a wait-free and linearizable implementation of any non-trivial concurrent
object or data structure that is shared among n processes. Thus, a
synchronization object such as compare-and-swap with an infinite consensus
number and the corresponding instruction can be viewed as "strong". On the
other hand, a synchronization object such as fetch-and-add with consensus
number two and the corresponding fetch-and-add instruction can be viewed as
"weak".
  Ellen et al. [2] observed recently that an object supporting two weak
instructions can also achieve infinite consensus number like an object that
supports one strong instruction. Using Herlihy's universal construction, this
implies that ignoring concerns about efficiency, one can design any concurrent
data structure or algorithm using only weak instructions. However, is it
possible that a combination of weak instructions is really powerful enough to
efficiently replace a strong instruction, like compare-and-swap, without
incurring a large overhead in time or space? In this paper, we answer this
question by giving an O(1) time wait-free and linearizable implementation of a
compare-and-swap register shared among n processes using read-write registers
and O(1) registers that support two synchronization primitives half-max and
max-write, each having consensus number one. Thus, any algorithm that solves
some arbitrary synchronization problem using read-write and compare-and-swap
registers can be transformed into an algorithm that has the same asymptotic
time complexity and only uses consensus number one instructions.
