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

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.


author = {James Aspnes},
title = {A one-bit swap using test-and-sets and a max register},
institution="Yale University Department of Computer Science",
year = 2012

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page