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(n4/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 ≤ 2n-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.
@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}
}