What question did this study set out to answer?

To present a method for formally proving the correctness of multiprocess programs using generalized inductive assertions.

March 1, 1977

Proving the Correctness of Multiprocess Programs

Key Points

To present a method for formally proving the correctness of multiprocess programs using generalized inductive assertions.
Generalization of the inductive assertion method for multiprocess programs.
Representation of processes with ordinary flowcharts without special synchronization mechanisms.
Hierarchical stepwise refinement for designing correctness proofs alongside programs.
Proofs are formalized and verifiable by machines, enhancing reliability.
Designed proofs align naturally with traditional informal proofs, improving practicality.
Method is applicable to a wide range of multiprocess programs without complex synchronization requirements.

Abstract

The inductive assertion method is generalized to permit formal, machine-verifiable proofs of correctness for multiprocess programs. Individual processes are represented by ordinary flowcharts, and no special synchronization mechanisms are assumed, so the method can be applied to a large class of multiprocess programs. A correctness proof can be designed together with the program by a hierarchical process of stepwise refinement, making the method practical for larger programs. The resulting proofs tend to be natural formalizations of the informal proofs that are now used.

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Cite this study

Leslie Lamport (Tue,) studied this question.

synapsesocial.com/papers/69fcb5bda6aa4a4c5afa43a1 — DOI: https://doi.org/10.1109/tse.1977.229904

Also consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Concurrent control with “readers” and “writers”· 1971 · 527 citations
Formal verification of parallel programs· 1976 · 790 citations
A multiprocessor system design· 1963 · 176 citations
An Axiomatic Proof Technique for Parallel Programs· 1978 · 47 citations
Axiomatic proof techniques for parallel programs.· 1975 · 132 citations

Authors

Leslie Lamport

Microsoft (United States)

Journals

IEEE Transactions on Software Engineering

Actions

Institutions

Abt Global (United States)

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Proving the Correctness of Multiprocess Programs

Key Points

Abstract

Citation Network

Connected Papers

Discussion

Cite this study

Also consider

Authors

Journals

Actions

Institutions

References and Citations

Citation Network

Connected Papers

Discussion

Also consider