While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points and need some verification and explanation.

In the first three sections of the paper, the authors presents constructions of useful concurrent data structures, including max register and counters with bounded values, with step complexity that is polylogarithmic in the number of values the object can take or the number of operations applied to it. Specifically (and extremely in brief),

The max register is an object $r$ supporting both WriteMax(r,t) and ReadMax(r) operations. It is recursively constructed from a tree of increasingly large max registers. The implementation is wait-free and linearizable.

The counter, supporting an CounterIncrement() operation and a ReadCounter() operation, is structured as a binary tree of max registers. The implementation is also wait-free and linearizable.

My problems are as follows:

(1) On the max register: What is the space complexity, i.e., the number of base objects of multi-writer multi-reader (MWMR, for short) registers, of the recursive implementation?

[[In my opinion:]] It is $2m - 1$ for there is exactly one MWMR register for each node in the tree. In particular, the tree can be thought of as the logic structure of an underlying array of $2m-1$ MWMR registers.

(2) Also on the max register: Is it possible to implement a max register with only a single MWMR register? Are there any related work?

[[(EDIT) In my opinion:]] I have found a related paper: Time and Space Lower Bounds for Non-blocking Implementations [@PODC'1996], in which Jayanti et al. show that

Operations must take $\Omega(n)$ space and $\Omega(n)$ steps in the worst case, for many common data structures, including (unbounded) max registers and (unbounded) counters, where $n$ is the number of concurrent processes.

However, I have not realized similar conclusions concerning about value-bounded data structures.

(3) On both the max register and the counter: Are there any related work on the max&min register supporting both ReadMax(r) and ReadMin(r)? Similarly, are there any related work on the inc&dec counter supporting both CounterIncrement() and CounterDecrement()?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.