Resource-oriented deadlock analysis

We present a method of detecting if deadlocks may occur in concurrent logic programs. Typical deadlock analysis is "process-oriented", being based on possible interleaving of processes. Our method is oriented towards the shared resources (communication channels, locks et cetera) and is based on orders in which individual resources are used by different processes. In cases where there are resources used by only a subset of all processes the search space can be dramatically reduced. The method arises very naturally out of the concurrent logic programming paradigm. Analysis of concurrent programs has previously used "coarsification" and "partial order" methods to reduce the search space. Our approach rediscovers and also extends these techniques. Our presentation is based around a logic programming pearl which finds deadlocked computations in a program which solves the dining philosophers problem.