Static analysis of multiway synchronization
Abstract
We present an algorithm for statically analyzing the communications amongst distributed or concurrent processes that communicate using multiway synchronization, in which many processes may participate in an atomic communication action, such as in the ITU standard specification language LOTOS. This extends our previous work in which we provided an algorithm for static analysis of communication amongst processes that use two-process primitives such as in CSP and Occam.
References
[1]
{1} K. R. Apt. A static analysis of CSP programs. In E. Clarke and D. Kozen, editors, Logics of Programs, volume 164 of Lecture Notes in Computer Science, pages 1-17. Springer Verlag, 1983.
[2]
{2} J.E. Cuny and L. Snyder. Conversion from data-driven to synchronous execution in loop programs. ACM Transactions on Programming Languages and Systems, 9(4):599-617, Oct 1987.
[3]
{3} C.A.R. Hoare. Communicating sequential processes. Communications of the ACM, 21(8):666-677, 1978.
[4]
{4} C.A.R. Hoare. Communicating Sequential Processes. Prentice Hall International, 1985.
[5]
{5} International Standards Organisation. Information Processing Systems - Open Systems Interconnection - LOTOS : A formal description technique based on temporal ordering of observational behavior, International Standard 8807, 1988.
[6]
{6} P.B. Ladkin and B.B. Simons. Compiletime analysis of communicating processes. In Proceedings of the Sixth ACM International Conference on Supercomputing, pages 248-259. ACM Press, 1992.
[7]
{7} P.B. Ladkin and B.B. Simons. Static Analysis of Interprocess Communication. Lecture Notes in Computer Science. Springer Verlag, 1994. To appear.
[8]
{8} P.B. Ladkin and B.B. Simons. Static deadlock analysis for CSP-type communications. In D. Fussell, editor, Responsive Computer Systems: Toward Integration of Fault- Tolerance and Real Time. Kluwer, 1994. To appear. Also in Proceedings of RCS-3, the Third International Workshop on Responsive Computer Systems, Lincoln, NH, Sept 1993, pp. 229-239.
[9]
{9} N. Mercouroff. An algorithm for analyzing communicating processes. Technical Report LIX/RR/90/12, Ecole Polytechnique, Laboratoire d'Informatique, Palaiseaux Cedex, France, 1990.
[10]
{10} R. Milner. Communication and Concurrency . Prentice Hall International, 1989.
Index Terms
- Static analysis of multiway synchronization
Recommendations
Static analysis of atomicity for programs with non-blocking synchronization
PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programmingIn concurrent programming, non-blocking synchronization is very efficient but difficult to design correctly. This paper presents a static analysis to show that code blocks are atomic, i.e., that every execution of the program is equivalent to one in ...
Comments
Information & Contributors
Information
Published In
October 1994
781 pages
Sponsors
- Industry Canada
- Natural Sciences and Engineering Research Council
- IBM Canada: IBM Canada
- NRC: National Research Council - Canada
Publisher
IBM Press
Publication History
Published: 31 October 1994
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 24 of 90 submissions, 27%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 141Total Downloads
- Downloads (Last 12 months)27
- Downloads (Last 6 weeks)5
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in