zbMATH — the first resource for mathematics

Static deadlock prevention in dynamically configured communication networks. (English) Zbl 1193.68161
Lodaya, Kamal (ed.) et al., Perspectives in concurrency. A Festschrift for P. S. Thiagarajan. Hyderabad: Universities Press; Boca Raton, FL: CRC Press (ISBN 978-1-4398-0943-3/hbk). 128-156 (2009).
Summary: We propose a technique to avoid deadlocks in a system of communicating processes. Our network model is very general. It supports dynamic process and channel creation and the ability to send channel endpoints over channels, thereby allowing arbitrary dynamically configured networks.
Deadlocks happen in such networks if there is a cycle created by a set of channels, and processes along the cycle circularly wait for messages from each other. Our approach allows cycles of channels to be created, but avoids circular waiting by ensuring that for every cycle \(C\), some process \(P\) breaks circular waits by selecting to communicate on both endpoints involved in the cycle \(C\) at \(P\). We formalize this strategy as a calculus with a type system. Our type system keeps track of markers called obstructions where wait cycles are intended to be broken. Programmers annotate message types with design decisions on how obstructions are managed. Using these annotations, our type checker works modularly and independently on each process,without suffering any state space explosion.
We prove the soundness of the analysis (namely deadlock freedom) on a simple but realistic language that captures the essence of such communication networks. We also describe how the technique can be applied to a substantial example.
For the entire collection see [Zbl 1162.68001].

68Q60 Specification and verification (program logics, model checking, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)