Our deadlock detector does not check for deadlock stability currently. It is possible that as the graph traversal progresses, locks which we were waiting on earlier get freed and suddenly become waiting on us, becoming counted in the cycle.

The fix would be to add check for deadlock stability by re-iterating the discovered cycle. Until this is fixed, we cannot use the deadlock deterministically for assertions, only for retries (which is what we already do).