Optimal Multi-Writer Multi-Reader Atomic Register

摘要

The wide gap in space complexity of atomic, multiwriter, multireader registerimplementations is addressed. While the space complexity of all previous implementations is linear, the lower bounds are logarithmic. Two implementations which close this gap are presented. The first implementation uses multireader physical registers while the second uses single reader physical registers. Both implementations are optimal with respect to the two most important complexity criteria: their space complexity is logarithmic and their time complexity is linear.