Where does deadlock collide?

A state in which a set of running processes are each blocked forever, because every one of them holds a resource that another in the set needs and waits for a resource that another holds, so the cycle can never resolve on its own. Coffman, Elphick, and Shoshani's 1971 System deadlocks surveyed the problem and named the four conditions that must all hold for it to arise: exclusive use of a resource, holding one resource while waiting for another, no forced release, and a closed loop of waiting. The referent is a fault in a computing system that designers work to prevent or detect, and it is not an abstract payoff structure that players prefer, nor a stalled legislature, since here every blocked process would rather proceed if only it could.[1]

Unit

A set of processes blocked in a closed wait cycle, none able to proceed

Recovery means

Broken by aborting or rolling back a process, or prevented by denying one of the four necessary conditions

Measured by

Detected by finding a cycle in the resource allocation graph, or inferred from processes that never make progress

A specific two-player, two-choice game in which each player's best move is to defect no matter what the other does, and, unlike the Prisoner's Dilemma, both players actually prefer the outcome where they both defect to the outcome where they both cooperate. Goforth and Robinson's 2005 The topology of the 2×2 games mapped every ordinally distinct 2×2 game and placed Deadlock among them, distinct from its better-known neighbour. The referent is a ranking of payoffs on paper that makes the uncooperative standoff the stable and jointly preferred result, so it is the opposite of a system fault: it is not a jammed computation that everyone wants unstuck, nor a legislature that cannot act.[2]

Unit

A payoff matrix over two players and two choices, ranked by preference

Recovery means

Not applicable

Measured by

Specified by the ordinal ranking each player assigns to the four possible outcomes

The inability of a divided government to change existing policy, where a bill stalls not because a majority opposes it but because the coalition needed to overcome a filibuster or a veto is too large to assemble. Krehbiel's 1998 Pivotal politics modelled this as a gridlock interval: a band of status-quo policies that no supermajority can be built to move, bounded by pivotal voters rather than by the median. The referent is a property of a lawmaking body under its own voting rules, gauged by how little passes, and it is neither a cycle of blocked computer processes nor an abstract game that players are content to be stuck in.[3]

Unit

A policy that cannot move because no coalition large enough to change it exists

Recovery means

Broken by elections that shift the pivotal voters, or by shocks that push the status quo outside the gridlock interval

Measured by

Gauged by legislative productivity, or by the width of the gridlock interval between pivotal voters