The bug report says the system hung. The engineer adds a timeout, the timeout fires, the hang is declared fixed, and the real defect, a structural cycle through a shared slave, waits for the next configuration. The timeout treated a deadlock as a performance problem. Naming the failure correctly decides the evidence: deadlock is argued on the dependency graph and shown as a stuck state, livelock as activity with no completion, starvation as service for everyone but one.
Deadlock means no progress is possible: each party waits for another in a cycle, so the system is stuck. The argument is structural, on the wait-for graph, and the temporal evidence is a reachable state with no enabled progress. Livelock means there is activity but no completion: parties keep moving, for example retrying against each other, and the completion counter never advances. Starvation means one requester is never served while others are: the system progresses, the victim does not. Circular wait is structural; absence of progress is temporal; a liveness counterexample, where the engine supports one, is a lasso, a finite prefix that reaches a loop round which the victim never wins.
Failure | Structural sign | Temporal sign | Arbiter example | Handshake chain example | Retry example (illustrative) |
|---|---|---|---|---|---|
Deadlock | cycle in the wait-for graph | stuck state, nothing enabled | grants withheld while requests are high (the arbiter proves it cannot: any request implies a grant) | valid waits for ready and ready waits for valid (next lessons) | two masters each hold one lock and wait for the other's |
Livelock | no cycle, retries possible | traffic with no completion | the granted requester drops and re-requests every cycle, no transfer completes | a stage keeps reissuing a beat that is never accepted | two masters keep retrying a transaction that a third keeps aborting |
Starvation | priority stuck on one side | others served, one waits | pointer frozen when requester 0 wins: requesters 1 to 3 starve (next lesson) | an upstream with priority always takes the shared stage | a retry loop that always loses to newer requests |
The checker below builds wait-for graphs for three small systems and reports cycles. The third graph carries an injected extra edge that closes a cycle, and the checker names it; the first two pass clean. The check is small, but every clause in it can fail: remove the cycle detection and the injected edge passes silently, which the assertions below guard against. The next lesson runs the same search on the real handshake lines of a chain:
def find_cycle(edges):
WHITE, GREY, BLACK = 0, 1, 2
colour = {}
def visit(node, stack):
colour[node] = GREY
for nxt in edges.get(node, []):
if colour.get(nxt, WHITE) == GREY:
return stack + [nxt]
if colour.get(nxt, WHITE) == WHITE:
hit = visit(nxt, stack + [nxt])
if hit:
return hit
colour[node] = BLACK
return None
for node in edges:
if colour.get(node, WHITE) == WHITE:
hit = visit(node, [node])
if hit:
return hit
return None
arbiter_ok = {"r0": ["arb"], "r1": ["arb"], "r2": ["arb"], "r3": ["arb"], "arb": []}
chain_ok = {"s1": ["s2"], "s2": ["sink"], "sink": []}
chain_bug = {"s1": ["s2"], "s2": ["s1"], "sink": []}
assert find_cycle(arbiter_ok) is None
assert find_cycle(chain_ok) is None
cycle = find_cycle(chain_bug)
assert cycle is not None and cycle[0] == cycle[-1]
assert "s1" in cycle and "s2" in cycle
print("PASS: no cycle in arbiter or clean chain; injected s1-s2 cycle named")The three terms are used with their definitions: a stuck system is not called starvation.
The wait-for graph is drawn for the actual configuration, including shared slaves and bridges.
The temporal evidence matches the claim: stuck state, completion counter, or per-requester waits.
Classify first, measure second. If nothing moves, draw the graph and look for the cycle before adding timeouts. If traffic flows but a completion counter stalls, suspect livelock and look for the retry loop. If all but one requester progress, read that requester's wait counter, which the arbiter lesson proves bounded.
Livelock: activity without completion. The proof is a completion counter that never advances despite the traffic, plus the retry loop identified as its cause. A timeout alone would only rename it.