Max registers, counters, and monotone circuits

ABSTRACT

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. The construction takes the form of a binary search tree: applying classic techniques for building unbalanced search trees gives an unbounded max register with cost O(min(log v, n)) to read or write a value v, where n is the number of processes.

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(Sd 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ⁿ⁻¹. 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.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 2: James Aspnes , Keren Censor, Approximate shared-memory counting despite a strong adversary, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.441-450, January 04-06, 2009, New York, New York
• 3: Hagit Attiya , Arie Fouren, Adaptive and Efficient Algorithms for Lattice Agreement and Renaming, SIAM Journal on Computing, v.31 n.2, p.642-664, 2001 [doi>10.1137/S0097539700366000]
• 4: J. L. Bentley and A. C.-C. Yao. An almost optimal algorithm for unbounded searching. Inf. Process. Lett., 5(3):82--87, 1976.
• 5: P. Elias. Universal codeword sets and representations of the integers. Information Theory, IEEE Transactions on, 21(2):194--203, 1975.
• 6: Faith Ellen Fich , Danny Hendler , Nir Shavit, Linear Lower Bounds on Real-World Implementations of Concurrent Objects, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.165-173, October 23-25, 2005 [doi>10.1109/SFCS.2005.47]
• 7: Michiko Inoue , Wei Chen, Linear-Time Snapshot Using Multi-writer Multi-reader Registers, Proceedings of the 8th International Workshop on Distributed Algorithms, p.130-140, September 29-October 01, 1994
• 8: Prasad Jayanti , King Tan , Sam Toueg, Time and Space Lower Bounds for Nonblocking Implementations, SIAM Journal on Computing, v.30 n.2, p.438-456, 2000 [doi>10.1137/S0097539797317299]
• 9: Ramesh Subramonian, Writing Sequential Programs for Parallel Processors: Implementation Experience, Proceedings of the Fourth International Conference on Computing and Information: Computing and Information, p.159-163, May 28-30, 1992
• 10: Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p.222-227, September 30-October 31, 1977

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
counters, distributed computing, max registers, monotone circuits, shared memory