CO7007 Communication and Concurrency
Convenor: Dr. I. Ulidowski
Three hour exam in May/June: 70%
This module provides students with an introduction to theories and applications of concurrency. In particular, it will familiarise students with the process algebras CCS (Calculus of Communicating Systems) and its operational semantics. The module will teach, via individual and collective work, how to specify, design and implement simple concurrent systems. Students will also learn how to verify correctness of concurrent systems using the Concurrency Workbench software tool.
Students should be able to: understand the notions of concurrency, communication, and concurrent systems; have a good knowledge of CCS and its operational and axiomatic semantics; be able to develop informal and formal specifications of simple concurrent systems, and be able to produce systems' designs from specifications; able to reason about the behaviour of simple concurrent systems, both by hand and with the aid of the Concurrency Workbench, using the techniques of equational reasoning and bisimulation.
Introduction. An introduction to concurrent and distributed systems, the notions of concurrency, communication and mobility, and a motivation for a formal theory of communication and concurrency.
Modelling concurrency and communication. An introduction, by means of examples, to the basic ideas and principles involved in the modelling of concurrency and communication. Transition rules, inference trees and transition graphs.
Process Algebras. Syntax and operational semantics of CCS.
Equational laws and algebraic reasoning. Equational laws for CCS and their justification. Techniques for equational reasoning.
Bisimulations Strong and weak bisimulations, strong and weak congruences (observational congruence). Techniques for establishing bisimulation equivalences, differences and relationships between various bisimulation relations. Compositional reasoning.
Case studies. Specifications and designs of simple concurrent systems in CCS. Verification of correctness using the Concurrency Workbench tool.
C.A.R. Hoare, Communicating Sequential Processes, Prentice-Hall 1985.
J.C. Baeten and W.P. Weijland, Process Algebra, Cambridge University Press 1990.
C. Fencott, Formal Methods for Concurrency, Thomson Computer Press 1996.
A.W. Roscoe, The Theory and Practice of Concurrency, Prentice-Hall 1997.
S. Schneider, Concurrent and Real-time Systems, Wiley 2000.
W. Fokkink, Introduction of Process Algebra, Springer 2000.
C. Stirling, Modal and Temporal Properties of Processes, Springer 2001.