James Aspnes. A one-bit swap object using test-and-sets and a max register. Available as YALEU/DCS/TR-1464, October 2012.
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 most three steps. Using standard randomized constructions, the max register and test-and-set bits can be replaced by read-write registers, at the price of raising the cost of a swap operation to an expected O(max(log n, min(log t, n))) steps, where t is the number of times the swap object has previously changed its value and n is the number of processes.
@techreport{Aspnes2012swap, author = {James Aspnes}, title = {A one-bit swap using test-and-sets and a max register}, institution="Yale University Department of Computer Science", number="YALEU/DCS/TR-1464", month=oct, year = 2012 }