A deadlock occurs in a network when two or more items prevent each other from moving. In a general model, items are kept at nodes and each node v has a buffer with capacity b(v). Given some initial placement for the items, and a route for each toward its destination, the Deadlock Problem asks whether the placement is safe, i.e., it is possible to take each item to its destination, or vice versa bound to deadlock. The problem is known to be hard on trees but, as soon as b >= 2, easy on general networks.
We sharpen and somehow explain this rather surprising complexity picture by means of two new tools: weak deadlocks (easy to recognize) and wise placements. A placement is wise if there are no items stored at nodes v with capacity one. We show that, for general networks and b, any initial placement that is wise and without weak deadlocks is safe. We strengthen this result for trees, where we also prove that a wise placement is safe only if it has no weak deadlocks.