A one-bit swap object using test-and-sets and a max register

James Aspnes

We describe a linearizable, wait-free implementation of a one-bit swap object from a single max register and an unbounded array of test-and-set bits. Each swap operation takes at m…