Abstract
We examine the “granularity” of statements of the form “await B → S”, where B is a boolean expression over program variables and S is a multiple-assignment. We consider two classes of such statements to have the same granularity iff any statement of one class can be implemented without busy-waiting by using statements of the other class. Two key results are presented. First, we show that statements of the form “await B → S” can be implemented without busywaiting by using simpler statements of the form “await X”, “X:= y”, and “y:=X”, where y is a private boolean variable and X is a shared singler-reader, multi-writer boolean variable. Second, we show that if busy-waiting is not allowed, then there is no general mechanism for implementing statements of the form “await B”, where B is an N-writer expression, using only assignment statements and statements of the form “await C”, where C is an (N - 1)-writer expression. It follows from these results that the granularity of waiting depends primarily on the number of processes that may write each program variable.
Work supported, in part, by NSF Contract CCR 9109497, and by the Center of Excellence in Space Data and Information Sciences. The first author was also supported by an award from the General Research Board at the University of Maryland.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit, “Atomic Snapshots of Shared Memory”, Proceedings of the Ninth Annual Symposium on Principles of Distributed Computing, 1990, pp. 1–14.
J. Anderson, “Composite Registers”, Proceedings of the Ninth Annual Symposium on Principles of Distributed Computing, 1990, pp. 15–30. To appear in Distributed Computing.
J. Anderson and M. Gouda, “A Criterion for Atomicity”, Formal Aspects of Computing: The International Journal of Formal Methods, Vol.4, No.3, May, 1992.
J. Anderson and B. Groselj, “Pseudo Read-Modify-Write Operations: Bounded Wait-Free Implementations”, Proceedings of the Fifth International Workshop on Distributed Algorithms, Lecture Notes in Computer Science 579, Springer-Verlag, pp. 52–70. Expanded version to appear in Science of Computer Programming.
G. Andrews, Concurrent Programming: Principles and Practice, The Benjamin/Cummings Publishing Company, Inc., Redwood City, California, 1991.
J. Aspnes and M. Herlihy, “Wait-Free Data Structures in the Asynchronous PRAM Model”, Proceedings of the Second Annual ACM Symposium on Parallel Architectures and Algorithms, July, 1990.
E. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliffs, New Jersey, 1976.
E. Dijkstra, “A Personal Summary of the Gries-Owicki Theory”, EWD554, March, 1976. In Selected Writings on Computing: A Personal Perspective, Springer-Verlag, New York, 1982.
M. Herlihy and J. Wing, “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, 1990, pp. 463–492.
K. Hwang and F. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, 1984.
A. Israeli and M. Li, “Bounded time-stamps”, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 1987, pp. 371–382.
J. Kessels, “Arbitration Without Common Modifiable Variables”, Ada Informatica, Vol. 17, 1982, pp. 135–141.
L. Lamport, “On Interprocess Communication, Parts I and II”, Distributed Computing, Vol. 1, 1986, pp. 77–101.
L. Lamport, “win and sin: Predicate Transformers for Concurrency”, ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, 1990, pp. 396–428.
M. Li, J. Tromp, and P. Vitanyi, “How to Construct Wait-Free Variables”, Proceedings of International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 372, Springer-Verlag, 1989, pp. 488–505.
J. Mellor-Crummey and M. Scott, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”, ACM Transactions on Computer Systems, Vol. 9, No. 1, February, 1991, pp. 21–65.
S. Owicki and D. Gries, “An Axiomatic Proof Technique for Parallel Programs I”, Acta Informatica, Vol. 6, 1976, pp. 319–340.
G. Peterson, “Myths About the Mutual Exclusion Problem”, Information Processing Letters, Vol. 12, No. 3, June, 1981, pp. 115–116.
J. Peterson and A. Silberschatz, Operating System Concepts, Addison-Wesley, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Anderson, J.H., Yang, JH., Gouda, M.G. (1992). The granularity of waiting (extended Abstract). In: Segall, A., Zaks, S. (eds) Distributed Algorithms. WDAG 1992. Lecture Notes in Computer Science, vol 647. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56188-9_21
Download citation
DOI: https://doi.org/10.1007/3-540-56188-9_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56188-0
Online ISBN: 978-3-540-47484-5
eBook Packages: Springer Book Archive