Abstract
Some well-known primitive operations, such as compare-and-swap, can be used, together with read and write, to implement any object in a wait-free manner. However, this paper shows that, for a large class of objects, including counters, queues, stacks, and single-writer snapshots, wait-free implementations using only these primitive operations and a large class of other primitive operations cannot be space efficient: the number of base objects required is at least linear in the number of processes that share the implemented object. The same lower bounds are obtained for implementations of starvation-free mutual exclusion using only primitive operations from this class. For wait-free implementations of a closely related class of one-time objects, lower bounds on the tradeoff between time and space are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, J.H., Kim, Y.J.: An improved lower bound for the time complexity of mutual exclusion. Distrib. Comput. 15(4), 221–253 (2002)
Anderson, J.H., Kim, Y.J., Herman, T.: Shared-memory mutual exclusion: major research trends since 1986. Distrib. Comput. 16(2–3), 75–110 (2003)
Burns, J.E., Lynch, N.A.: Bounds on shared memory for mutual exclusion. Information and Computation 107(2), 171–184 (1993)
Cypher, R.: The communication requirements of mutual exclusion. In: Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 147–156 (1995)
Dwork, C., Herlihy, M., Waarts, O.: Contention in shared memory algorithms. J. ACM 44(6), 779–805 (1997)
Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing.Distrib. Comput. 16(2–3), 121–163 (2003)
Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)
Jayanti, P.: A time complexity lower bound for randomized implementations of some shared objects. In: Proceedings of the 17th Annual ACM Symposium on Principles of Distrib. Comput., pp. 201–210 (1998)
Jayanti, P., Tan, K., Toueg, S.: Time and space lower bounds for non-blocking implementations. Siam J. Comput. 30(2), 438–456 (2000)
Yang, J.H., Anderson, J.H.: A fast, scalable mutual exclusion algorithm. Distrib. Comput. 9(1), 51–60 (1995)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fich, F.E., Hendler, D. & Shavit, N. On the inherent weakness of conditional primitives. Distrib. Comput. 18, 267–277 (2006). https://doi.org/10.1007/s00446-005-0136-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-005-0136-5