An error in EWD744.

When Scholten and I tried this morning to prove the correctness of the assertion made in the Note on page EWD744-2, we encountered difficulties, which were only resolved by finding a counterexample.

EWD754 figure 1

Obviously the six edges p, q, a, b, c, and d can not be ordered in a way with which pab, qbc, pcd, and qda are compatible. It is also easily verified that the four-process system, in which the processes claim three resources in the given orders, is deadlock-free. All by itself the cyclic path (a,b,c,d) could cause deadlock, but the shared resources p and q —even one of them would have sufficed— prevent the deadlock. The counterexample is symmetric in the four processes!


Plataanstraat 5
5671 AL NUENEN
The Netherlands
17 October 1980
prof. dr. Edsger W.Dijkstra
Burroughs Research Fellow