# 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.

## Abstract

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.

## BibTeX

Download@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
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page