  The well-known randomized consensus algorithm by Aspnes and Herlihy for
asynchronous shared-memory systems was proved to work, even against a strong
adversary, under the assumption that the registers that it uses are atomic
registers. With atomic registers, every read or write operation is
instantaneous (and thus indivisible). As pointed out by Golab et al. (2011),
however, a randomized algorithm that works with atomic registers does not
necessarily work if we replace the atomic registers that it uses with
linearizable implementations of registers.
  This raises the following question: does the randomized consensus algorithm
by Aspnes and Herlihy still work against a strong adversary if we replace its
atomic registers with linearizable registers? We show that the answer is
affirmative, in fact, we show that even linearizable registers are not
necessary. More precisely, we prove that the algorithm by Aspnes and Herlihy
works against a strong adversary even if the algorithm uses only regular
registers.
