 <p>Here is an example, the simplest possible probably. We have machines <code>A</code> and <code>B</code>. Machine A has locks <code>T1</code> and <code>T2</code> with the relationship <code>T1 &lt; T2</code>. Machine <code>B</code> has <code>T3</code> and <code>T4</code> with <code>T3 &gt; T4</code>.</p> <p>Now, the local graphs are just that T2 must wait for T1 and T3 must wait for T4. So there are no local cycles. But now, assume we have <code>T4 &lt; T1</code> so T1 has to wait for T4. And at the same time <code>T2 &lt; T3</code> so T3 has to wait for T2. In this case, there is a cycle globally.</p> <p>So how does that cycle happen? The key here is that you never have the full information in a distributed system. So we may learn later that the inter-machine dependencies are there. And then we have a problem.</p>