James Aspnes, Hagit Attiya, and Keren Censor-Hillel.
Polylogarithmic concurrent data structures from monotone circuits.
*Journal of the Association for Computing Machinery*,
59(1):2:1–2:24, February 2012.
An earlier version appeared
in
Twenty-Eighth Annual ACM Symposium on Principles of Distributed Computing, August 2009, pp. 36–45,
under the title
“Max registers, counters, and monotone circuits.”

A method is given for constructing a *max register*, a
linearizable, wait-free concurrent data structure that supports a
write operation and a read operation that returns the largest
value previously written. For fixed m, an m-valued max
register can be constructed from one-bit multi-writer multi-reader
registers at a cost of at most ⌈lg m⌉ atomic register
operations per write or read.

It is also shown how a max register can be used to transform any
monotone circuit into a wait-free concurrent data structure that
provides write operations setting the inputs to the circuit and a
read operation that returns the value of the circuit on the
largest input values previously supplied. The cost of a write is
bounded by O(S d min(⌈lg m⌉, n), where m is the
size of the alphabet for the circuit, S is the number of gates
whose value changes as the result of the write, and d is the
number of inputs to each gate; the cost of a read is
min(⌈lg m⌉, O(n)). While the resulting data
structure is not linearizable in general, it satisfies a weaker
but natural consistency condition. As an application, we obtain a
simple, linearizable, wait-free counter implementation with a cost
of O(min(log n log v, n)) to perform an increment and
O(min(log v, n)) to perform a read, where v is the current
value of the counter. For polynomially-many increments, this
becomes O(log² n), an exponential improvement on the best
previously known upper bounds of O(n) for an exact counting and
O(n^{4/5+ε}) for approximate counting.

Finally, it is shown that the upper bounds are almost optimal. We
prove that min(⌈lg m⌉, n-1) is a lower bound on the
worst-case complexity for any solo-terminating deterministic
implementation of an m-valued bounded max register, which is
exactly equal to the upper bound for m ≤ 2^{n-1}. The same
bound also holds m-valued counters. Furthermore, even in a
solo-terminating randomized implementation of an n-valued max
register with an oblivious adversary and global coins, there exist
simple schedules containing n-1 partial write operations and one
read operation in which, with high probability, the worst-case
step complexity of a read operation is Ω(log n / log log
n) if the write operations have polylogarithmic step complexity.

- PODC 2009 proceedings version: PDF.
- JACM version:
**PDF**. - Slides from Keren Censor's prize-winning PODC 2009 talk: PPTX.
- Slides from James Aspnes's 2009 talk at Dartmouth: PDF.

@article{AspnesAC2012, author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel}, title = {Polylogarithmic concurrent data structures from monotone circuits}, journal=jacm, month=feb, year = 2012, volume=59, number=1, pages={2:1--2:24} }

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page