Parameterized refinement is a refinement technique for preserving specific linear time temporal logic properties during formal program development. In this paper, we describe a proof method for verifying that one program is a parameterized refinement of another program. Our method combines transduction, due to Jonsson, Pnueli, and Rump, for showing that one system simulates another system, with techniques used in implementations of model checkers. The method is argued to be attractive in a development environment, where tools such as model checkers are applied. It enables rigorous verification that one system is a parameterized refinement of another system.

Abstract Compositional proof systems for shared variable concurrent programs can be devised by including the interference information in the specifications. The formalism falls into a category called rely-guarantee (or assumption-commitment) , in which a specification is explicitly (syntactically) split into two corresponding parts. This paper summarises existing work on the rely-guarantee method and gives a systematic presentation. A proof system for partial correctness is given first, thereafter it is demonstrated how the relevant rules can be adapted to verify deadlock freedom and convergence. Soundness and completeness, of which the completeness proof is new, are studied with respect to an operational model. We observe that the rely-guarantee method is in a sense a reformulation of the classical non-compositional Owicki & Gries method, and we discuss throughout the paper the connection between these two methods.

Abstract Our own basic intuitions are presented when introducing the method developed by Abadi and Lamport in [AbL88a] for proving refinement between specifications of nondeterministic programs correct to people unacquainted with it. The example we use to illustrate this method is a nontrivial communication protocol that provides a mechanism analogous to message passing between migrating processes within a fixed finite network of nodes due to Kleinman, Moscowitz, Pnueli and Shapiro [KMP91]. Especially the cruel last step of a three step refinement proof of that protocol gives rise to a deeper understanding of, and some small enhancements to, Abadi and Lamport's 1988 method.

Abstract Designers of network algorithms often give elegant informal descriptions of the intuition behind their algorithms (see [ GHS83 , Hum83 , MeS79 , Seg82 , Seg83 , ZeS80 ]). Usually these descriptions are structured as if subtasks are performed one after the other. Although these subtasks are performed sequentially from a logical point of view, they are performed concurrently from an operational point of view. The current paper presents a principle for formally designing and verifying these kinds of algorithms. It is formulated in Manna and Pnueli’s linear time temporal logic [ MaP83 , MaP92 ]. This principle is applicable to large classes of algorithms, such as those for computing minimum-paths, connectivity, network flow, and minimum-weight spanning trees.

He Jifeng and Hoare's [He Jifeng] approach to integrate theories for "program8 as predicates" and "programs as predicate transformers"in sequential setting i generalieed to a compositional verification theory for concurrency, using idea8 of Zwiers' [Zwiers].Due to the generality of the approach, a variety of parallel composition operators, based on shared variables, communication events, interleaving, maximal progress and the like, can be expressed as derived operations.

We present a fully abstract semantics for real-time distributed computing of the Ada and OCCAM kind in a denotational style. This semantics turns termination, communication along channels, and the time communication takes place, into observables. Yet it is the coarsest semantics to do so which is syntax-directed (this is known as full abstraction). It extends the linear history semantics for CSP of Francez, Lehman and Pnueli. Our execution model is based on maximizing concurrent activity as opposed to interleaving (in which only one action occurs at the time and arbitrary delays are incurred between actions). It is a variant of the maximal parallelism model of Salwicki and Müldner.

This paper indicates a method of describing real-time processes and their asynchronous communication by means of message exchanges. This description method is based upon an extension of linear time temporal logic to a special temporal logic in which real-time and asynchronous message passing properties can be expressed. We give a model of this logic, define new operators and show amongst others how they can be applied to specify real-time asynchronous message passing and an abstract real-time transmission medium.

An axiomatic proof system is presented for proving partial correctness and absence of deadlock (and failure) of communicating sequential processes. The key (meta) rule introduces cooperation between proofs, a new concept needed to deal with proofs about synchronization by message passing. CSP's new convention for distributed termination of loops is dealt with. Applications of the method involve correctness proofs for two algorithms, one for distributed partitioning of sets, the other for distributed computation of the greatest common divisor of n numbers.

How can one organize the understanding of complex algorithms? People have been thinking about this issue at least since Euclid first tried to explain his innovative greatest common divisor algorithm to his colleagues, but for current research into verifying state-of-the-art programs, some precise answers to the question are needed. Over the past decade the various verification methods which have been introduced (inductive assertions, structural induction, least-fixedpoint semantics, etc.) have established many basic principles of program verification (which we define as: establishing that a program text satisfies a given pair of input-output specifications). However, it is no coincidence that most published examples of the application of these methods have dealt with "toy programs" of carefully considered simplicity.Experience indicates that these "first generation" principles, with which one can easily verify a three-line greatest common divisor algorithm, do not directly enable one to verify a 10,000 line operating system (or even a 50 line list-processing algorithm) in complete detail. To verify complex programs, additional techniques of organization, analysis and manipulation are required. (That a similar situation exists in the writing of large, correct programs has long been recognized -- structured programming being one solution.)This paper examines the usefulness of correctness-preserving program transformations (see [6]) in structuring fairly complex correctness proofs. Using our approach one starts with a simple, high-level (or "abstract") algorithm which can be easily verified, then successively refines it by implementing the abstractions of the initial algorithm to obtain various final, detailed algorithms. In Section 2 we introduce the technique by deriving the Deutsch-Schorr-Waite list-marking algorithm [14]. Our main example is the more complex problem of verifying bounded-workspace list-copying algorithms: Section 3 defines the issues, Section 4 presents the key intermediate algorithm in detail and Section 5 considers three of the most complex (published) implementations of list-copying, one of which is discussed in detail. In Section 6 we make some general remarks on program verification and the relevance of our results to the (larger) field of program correctness; Section 7 mentions some related work.