Elements of concurrent programming (Third edition)

These lecture notes are intended to introduce the reader to the basic notions of nondeterministic and concurrent programming. We start by giving the operational semantics of a simple deterministic language and the operational semantics of a simple nondeterministic language based on guarded commands. Then we consider concurrent computations based on: (i) vectorization, (ii) shared variables, and (iii) handshaking communications à la CCS (Calculus for Communicating Systems) [16]. We also address the problem of mutual exclusion and for its solution we analyze various techniques such as those based on semaphores, critical regions, conditional critical regions, and monitors. Finally, we study the problem of detecting distributed termination and the problem of the serializability of database transactions. Sections 1, 2, and 6 are based on [16,22]. The material of Sections 3 and 4 is derived from [1,2,4,5,7,8,13,18,20]. Section 5 is based on [10] and is devoted to programming examples written in Java where the reader may see in action some of the basic techniques described in these lecture notes. In Section 7 we closely follow [3]. We would like to thank Dr. Maurizio Proietti for his many suggestions and his encouragement, Prof. Robin Milner and Prof. Matthew Hennessy for introducing me to CCS, Prof. Vijay K. Garg from whose book [10] I learnt concurrent programming in Java, my colleagues at Roma Tor Vergata University for their support and friendship, and my students for their patience and help. Many thanks also to Dr. Gioacchino Onorati and Lorenzo Costantini of the Aracne Publishing Company for their kind and helpful cooperation. Roma, April 2005 In the third edition we have corrected a few mistakes, we have improved Chapter 2, and we have added in the Appendix a Java program for the distributed computation of spanning trees of undirected graphs. Thanks to Dr. Emanuele De Angelis for discovering an error in the presentation of Peterson’s algorithm. Roma, January 200