Logics and Models of Concurrent Systems

1. Front Matter

   Pages I-VIII

   PDF

2. Temporal Logic

   1. Front Matter

      Pages 1-1

      PDF

   2. Using Temporal Logic for Automatic Verification of Finite State Systems

      • E. M. Clarke, M. C. Browne, E. A. Emerson, A. P. Sistla

      Pages 3-26

   3. Resolution Modal Logics

      • Luis Fariñas-del-Cerro

      Pages 27-55

   4. Tools for Verifying Network Protocols

      • Brent Hailpern

      Pages 57-76

   5. An Axiomatic Semantics of Concurrent Programming Languages

      • Leslie Lamport

      Pages 77-122

   6. In Transition From Global to Modular Temporal Reasoning about Programs

      • Amir Pnueli

      Pages 123-144

3. Syntax Directed Verification Methods

   1. Front Matter

      Pages 145-145

      PDF

   2. Correctness Proofs of Distributed Termination Algorithms

      • Krzysztof R. Apt

      Pages 147-167

   3. Script: A Communication Abstraction Mechanism and its Verification

      • Nissim Francez, Brent Hailpern, Gadi Taubenfeld

      Pages 169-212

   4. The Cooperation Test : a syntax-directed verification method

      • Willem P. de Roever Jr.

      Pages 213-257

4. Around CCS, Theoretical CSP and Distributed Systems

   1. Front Matter

      Pages 259-259

      PDF

   2. Notes on Algebraic Calculi of Processes

      • G. Boudol

      Pages 261-303

   3. Deadlock Analysis in Networks of Communicating Processes

      • S. D. Brookes, A. W. Roscoe

      Pages 305-323

   4. A Paradigm for Detecting Quiescent Properties in Distributed Computations

      • K. Mani Chandy, Jayadev Misra

      Pages 325-341

   5. About Fair Asynchrony

      • Philippe Darondeau

      Pages 343-368

   6. A Logic for the Specification and Proof of Controllable Processes of CCS

      • Susanne Graf, Joseph Sifakis

      Pages 369-395

   7. Specification-Oriented Programming in TCSP

      • Ernst-Rüdiger Olderog

      Pages 397-435

5. Miscellaneous

   1. Front Matter

      Pages 437-437

      PDF

   2. Theoretical Foundations for Non-Monotonic Reasoning in Expert Systems

      • D. M. Gabbay

      Pages 439-457

The cooperation test [Apt, Francez & de Roever] was originally conceived to capture the proof theoretical analogue of distributed message exchange between disjoint processes, as opposed to the interference freedom test [Owicki & Gries], being the proof theoretical analogue of concurrent communication by means of interference through jointly shared variables. Some authors ([Levin & Gries, Lamport & Schneider, Schlichting and Schneider]) stress that both forms of communication can be proof theoretically characterized using interference freedom only, since proofs for both ultimately amount to an invariance proof of a big global assertion [Ashcroft], invariance of whose parts amounts to interference freedom. Yet I feel that the characteristic nature of the cooperation test is still preserved in the analysis of these authors, because in their analysis of CSP the part dealing with interference freedom specializes to maintenance of a global invariant, the expression of which requires per process the introduction of auxiliary variables which are updated in that process only, thus preserving the concept of disjointness (as opposed to sharing), since now all variables from different processes are disjoint. The cooperation test has been applied to characterize concurrent communication as occurring in Hoare's Communicating Sequential Processes (CSP) [Hoare 2], Ichbiah's ADA [ARM], and Brinch Hansen's Distributed Processes (DP) [Brinch Hansen]. This characterization has been certified through soundness and completeness proofs [Apt 2, Gerth]. As in the interference freedom test this characterization consists of two stages, a local sequential stage and a global stage.

• Invariant
• Programm
• Systems
• algorithms
• communicating sequential process
• cooperation
• distributed systems
• form
• logic
• maintenance
• programming
• programming language
• semantics
• sound
• verification

• L.I.T.P., Université Paris 7, Paris, France

  Krzysztof R. Apt

Policies and ethics