Introduction to Concurrency Theory
Computer systems, implemented in hardware or software or as a combination of both, are supposed to offer certain well-specified services, so that their users can safely rely on them. However, often a computer system is not equipped with a proof that the specified service or property is guaranteed. In order to do so, one has first to define an abstract semantic model of the system (the specification), that can be used to study whether it satisfies the requested property. If so, then one has to use such a specification as the reference model to build the actual executable implementation, and possibly prove that the implementation is compliant with the specification. We call this production methodology the specification-verification-implementation methodology.
This kind of production methodology is largely used in more traditional and wellestablished engineering disciplines, such as in construction engineering, where a model of a construction, e.g., a bridge, is always designed, studied and proved correct, before being constructed. By contrast, in computer science and engineering this approach has been used extensively only recently, after some astonishing incidents in the 1990s, such as Intel’s Pentium II bug in the floating point division unit in 1994. It is still common practice today to go directly to implementation: too often the specification-verification phases are missing (or are only very sketchy and informal), and correctness of the implementation is checked by testing a posteriori; however, as Dijkstra [Dij69] observed: “testing can be used to show the presence of bugs, but never to show their absence”. Therefore, if the formal guarantee of correctness is a necessary requirement of the system, a formal specification must be provided and used as a basis to prove the correctness of the design first, and then, possibly, also of the implementation.
An important reason why the specification-verification-implementation methodology is not so widespread in computer engineering is the current limitations of the theoretical tools that can be used in support. On the one hand, semantic theories for modeling computer systems are often not easy, or are even mathematically difficult, so that an engineer would certainly not spend time on it, unless the payoff is very rewarding. In some cases, indeed, the effort is worthwhile: nowadays there is an increasing number of success stories, mainly related to hardware verification. On the other hand, there are intrinsic mathematical limitations to verification that are rooted in classic undecidable problems of computability theory, such as the halting problem (see Section 1.3.5). Therefore, in some cases, we are forced to live with partially unverified systems.
This book aims at offering a simple, introductory theory of concurrent, reactive systems that is mathematically well-defined, rich enough to offer mathematical tools for verification and expressive enough to model nontrivial, sometimes even complex systems. It is based on the semantic model of labeled transition systems [Kel76] and on the language CCS, proposed by Robin Milner [Mil80, Mil89, Mil99]. The main verification technique is based on equivalence-checking, where an abstract model of a system, described as a CCS process, is compared with a more detailed implementation of it, expressed in the same language.We will see that this technique is useful in some remarkable cases.
Of course, this simple theory does not cover all the possible aspects of the behavior of real-life systems; for instance, we are not dealing with real-time or mobility issues; nonetheless, extensions of this theory to include such additional features are possible, already well-investigated and can be profitably studied in more specific books, such as the second part of [AILS07] for real time or [SW01] for mobility.
The following subsections provide a historical perspective on the problem of the semantics of concurrency, which has led to the ideas that are at the base of the theory presented in this textbook.
- File Type: PDF
- Upload Date: September 4, 2015
Do you like this book? Please share with your friends!
How to Read and Open File Type for PC ?
- Adult Material
- Adult Novels
- Audio Books
- Comics & Graphic Novels
- Computer Science
- Electrical Engineering
- Fantasy Novels
- Fiction Other
- Finances and Money
- For Children
- Graphic Design
- Health and Care
- Health and Fitness
- Pets & Animal Care
- Science Engineering
- Web Development
You may also be interested in the following ebook:
- Douglas K. Barry and David Dick
- Shon Harris
- Angeliki Alexiou
- Ronald W. Larsen
- Lora D. Delwiche and Susan J. Slaughter
- Edgar Jacoby
- Robert Martin
- Earnest Wish