Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10330632 | Information and Computation | 2005 | 45 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amos Israeli, Amnon Shaham,