Programming Research Group Technical Monograph PRG-57

A W Roscoe and Naiem Dathi

November 1986, 38 pages, ISBN 0-902928-38-4

We introduce some combinatorial techniques for establishing the deadlock freedom of concurrent systems which are similar to the variant/invariant method of proving loop termination. Our methods are based on the local analysis of networks, which is combinatorially far easier than analysing all global states. They are illustrated by proving numerous examples to be free of deadlock, some of which are useful classes of network.