Concurrency theory


Aim of the course

Presenting the idea of concurrent programming and analysis of concurrent systems through their formal modeling. It covers the issues of managing the functioning of concurrent applications in various computing environments.

Lecture programme

Lamport model, definitions of sequential and concurrent programming, stop condition and partial correctness, viability, safety and fairness, implementation context of concurrent processing, tools, operating system, multi-processor environment, message-passing environment, virtual environments, multiagent systems, Dekert-Mazurkiewicz traces, Foaty normal form, dependences graph, distributed systems modeled by traces, FIFO and CO communication, Charon theorem of uniqueness of representation, sub-optimal scheduling for traces, time vector, elements of CSP, concurrent execution of processes, guarded alternatives, guard arrays, loop construct, parallel execution of instructions, blocking communication, rendezvous, examples, Petri nets - general introduction, networks of places and transitions, algebraic representation, invariants of places and transitions, reachability graphs, interpretation of the condition of vitality, algorithms for finding deadlocks and traps, elements of the analysis of systems with time constraints

Overview of the course elements

Laboratory exercises are divided into three thematic groups: A – Mechanisms of synchronization and communication of processes and threads, B - Properties of the classic problems of concurrency, and C - Models of concurrent systems. The first group involves the mechanisms provided by JVM (semaphores, monitors, locks, concurrent data structures), Erlang (asynchronous communication). The second group is trained using the Reactor and Proactor patterns. In the third group we focus on the creation and validation of models based on CSP, Petri nets and Dekerta-Mazurkiewicz traces. Models and exercises are based on the classic problems of concurrency and important instances of concurrent numerical computations.

Reading list

1. Roscoe A., W.; The Theory and Practice of Concurrency. Prentice Hall 1998.
2. Weiss Z., Gruźlewicz T.; Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT 1994.
3. Starke P., H.; Sieci Petri, podstawy, zastosowania, teoria. PWN 1987.
4. Iszkowski W., Maniecki M.; Programowanie współbieżne. WNT 1982.
5. Charron B, Delporte-Gallet C, Fauconnier H; How to model a distributed computation, Instute Blaise Press, Paris, 1993.

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards