Optimal multi-writer multi-reader atomic register
Amos Israeli, Amnon Shaham · 1992
Two implementations of a multi-writer, multi-reader, atomic register are presented. The physical registers used by the first implementation are single-writer, multi-reader, atomic registers; the physical registers used by the second implementation are single-reader, single-writer, atomic registers. Both implementations are optimal with respect to the two most important complexity criteria: In both implementation the space complexity is logarithmic, thus matching the lower bound proven by Cori and Sopena; and the time complexity is linear, thus matching the obvious lower bound. These implementations improve upon the space complexity of all previous implementations in their respective classes, by an exponential factor.