Time and space optimal implementations of atomic multi-writer register

摘要

This paper addresses the wide gap in space complexity of atomic, multi-writer, multi-reader register implementations. While the space complexity of all previous implementations is linear, the lower bounds are logarithmic. We present three implementations which close this gap: the first implementation is sequential and its role is to present the idea and data structures used in the second and third implementations. The second and third implementations are both concurrent, the second uses multi-reader physical registers while the third uses single-reader physical registers. Both the second and third implementations are optimal with respect to the two most important complexity criteria: their space complexity is logarithmic and their time complexity is linear. (c) 2005 Elsevier Inc. All rights reserved.