The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Formal verification of parallel programs
Open accessAbstract
Two formal models for parallel computation are presented: an abstract conceptual model and a parallel-program model. The former model does not distinguish between control and data states. The latter model includes the capability for the representation of an infinite set of control states by allowing there to be arbitrarily many instruction pointers (or processes) executing the program. An induction principle is presented which treats the control and data state sets on the same ground. Through the use of “place variables,” it is observed that certain correctness conditions can be expressed without enumeration of the set of all possible control states. Examples are presented in which the induction principle is used to demonstrate proofs of mutual exclusion. It is shown that assertions-oriented proof methods are special cases of the induction principle. A special case of the assertions method, which is called parallel place assertions, is shown to be incomplete. A formalization of “deadlock” is then presented. The concept of a “norm” is introduced, which yields an extension, to the deadlock problem, of Floyd's technique for proving termination. Also discussed is an extension of the program model which allows each process to have its own local variables and permits shared global variables. Correctness of certain forms of implementation is also discussed. An Appendix is included which relates this work to previous work on the satisfiability of certain logical formulas.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Assigning meanings to programs
Floyd, R. W. (1967) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/019/0235771 · Cited by 1,408
Hierarchical ordering of sequential processes
Dijkstra, E. (1971) · Acta Informatica · doi:10.1007/bf00289519 · Cited by 797
Prevention of system deadlocks
Habermann, A. N. (1969) · Communications of the ACM · doi:10.1145/363156.363160 · Cited by 321
A multiprocessor system design
Conway, M. E. (1963) · Proceedings of the November 12-14, 1963, fall joint computer conference on XX - AFIPS '63 (Fall) · doi:10.1145/1463822.1463838 · Cited by 175
Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
Keller, R. (1973) · Journal of the ACM · doi:10.1145/321765.321782 · Cited by 75
Self-citation
Cited by
Petri nets: Properties, analysis and applications
Murata, T. (1989) · Proceedings of the IEEE · doi:10.1109/5.24143 · Cited by 10,606
The temporal logic of programs
Pnueli, A. (1977) · 18th Annual Symposium on Foundations of Computer Science (sfcs 1977) · doi:10.1109/sfcs.1977.32 · Cited by 5,689
Lamport, L. (1994) · ACM Transactions on Programming Languages and Systems · doi:10.1145/177492.177726 · Cited by 1,843
Specification and verification of concurrent systems in CESAR
Queille, J. P., & Sifakis, J. (1982) · Lecture Notes in Computer Science · doi:10.1007/3-540-11494-7_22 · Cited by 1,321
Peterson, J. L. (1977) · ACM Computing Surveys · doi:10.1145/356698.356702 · Cited by 1,179
Proving the Correctness of Multiprocess Programs
Lamport, L. (1977) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1977.229904 · Cited by 1,138
The oracle problem in software testing: A survey
Barr, E. T., Harman, M., McMinn, P., Shahbaz, M., & Yoo, S. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2014.2372785 · Cited by 1,104
Performance Analysis Using Stochastic Petri Nets
Molloy (1982) · IEEE Transactions on Computers · doi:10.1109/tc.1982.1676110 · Cited by 1,071
The temporal semantics of concurrent programs
Pnueli, A. (1981) · Theoretical Computer Science · doi:10.1016/0304-3975(81)90110-9 · Cited by 699
Abstract interpretation and application to logic programs
Cousot, P., & Cousot, R. (1992) · The Journal of Logic Programming · doi:10.1016/0743-1066(92)90030-7 · Cited by 582
Proving Liveness Properties of Concurrent Programs
Owicki, S., & Lamport, L. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357178 · Cited by 576
Logics and models of real time: A survey
Alur, R., & Henzinger, T. A. (1992) · Lecture Notes in Computer Science · doi:10.1007/bfb0031988 · Cited by 548
Concepts and Notations for Concurrent Programming
Andrews, G. R., & Schneider, F. B. (1983) · ACM Computing Surveys · doi:10.1145/356901.356903 · Cited by 520
Proofs of Networks of Processes
Misra, J., & Chandy, K. M. (1981) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1981.230844 · Cited by 493
The origins of structural operational semantics
Plotkin, G. D. (2004) · The Journal of Logic and Algebraic Programming · doi:10.1016/j.jlap.2004.03.009 · Cited by 362
A Classification of Security Properties for Process Algebras1
Focardi, R., & Gorrieri, R. (1995) · Journal of Computer Security · doi:10.3233/jcs-1994/1995-3103 · Cited by 314
Finite state description of communication protocols
Bochmann, G. V. (1978) · Computer Networks (1976) · doi:10.1016/0376-5075(78)90015-6 · Cited by 283
Metadata
- Authors
- Keller, R. M.
- Venue
- Communications of the ACM
- Published
- 1976-07
- Volume
- 19
- Issue
- 7
- Pages
- 371-384
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W1994350081
- Cited by
- 797
- References
- 5
- FWCI
- 15.33
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.