This week I gave a talk at my university on true concurrency. My main focus, although, was partial-order semantics for Petri nets.
Computer scientists have been paying attention concurrency and parallelism since the dawn of the computing as science. In this talk I would like to discuss the topic called true concurrency – the concurrency in presence of parallelism, as opposed to concurrency defined by interleaving.
Carl Adam Petri played a crucial role in the area of true concurrency, he was interested in analyzing the relations and connections between the abstract machines (that of Turing, Church and others) and their physical counterparts. Petri observed that the assumption of the global state is unrealistic in big systems and he proposed to replace the “execution semantics’’ with the semantics of”nonsequential proceses’’, the notion which gave rise to the theory of occurrence nets and unfoldings. That corpus of work has be introduced originally to solve the very theoretical problem: to give precise semantics to concurrent systems. Goltz, Reisig, Nielsen, Plotkin, Winskel, Engelfreit, Montanari are among the people who have contributed to the topic.
Later on, with the rise of model checking techniques, it has been discovered that partial-order semantics (unfoldings) may be used in practice for formally verifying systems. McMillan, Esparza, Romer, Vogler, Khomenko and others have pioneered what is now can be called a “partial order approach to model checking”.
True concurrency is still a thriving field, and in my talk I hope to touch the foundations, as well as pragmatic applications of the approaches derived from the theoretical foundations of the subject.