  Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and
Zhu has shown that computability does not require multicore architectures to
support "strong" synchronization instructions like compare-and-swap, as opposed
to combinations of "weaker" instructions like decrement and multiply. However,
this is the status quo, and in turn, most efficient concurrent data-structures
heavily rely on compare-and-swap (e.g. for swinging pointers and in general,
conflict resolution).
  We show that this need not be the case, by designing and implementing a
concurrent linearizable Log data-structure (also known as a History object),
supporting two operations: append(item), which appends the item to the log, and
get-log(), which returns the appended items so far, in order. Readers are
wait-free and writers are lock-free, and this data-structure can be used in a
lock-free universal construction to implement any concurrent object with a
given sequential specification. Our implementation uses atomic read, xor,
decrement, and fetch-and-increment instructions supported on X86 architectures,
and provides similar performance to a compare-and-swap-based solution on
today's hardware. This raises a fundamental question about minimal set of
synchronization instructions that the architectures have to support.
