The basic idea is to give a description of what can happen when several processes are modifying shared ressources. Given a shared resource

Figure 1: Example of a progress graph

The shaded area represents states which are not allowed in any execution path, since they correspond to mutual exclusion. Such states constitute the

Figure 2: The corresponding request graph

Figure 3: The progress graph corresponding toPa.Va.Pb.Vb|Pa.Va.Pb.Vb

There is another method to determine deadlocks in such situations, which was of course known long ago and was entirely graph-theoretic, known as the

Figure 4: The progress graph corresponding toPb.Vb.Pa.Va|Pa.Va.Pb.Vb

Starting from progress graphs, the article [Coffman et al., 1971] developed an algorithm in