Two chips are connected by a link with a small receive buffer at each end. Each chip sends read requests to the other and answers the reads it receives. Under light load it runs for days. Under a burst, both chips send requests at the same moment, both receive buffers fill with requests, and each chip can serve a request only by sending a response, into a buffer that is full of the other chip's requests. The link is perfectly healthy and nothing moves.

Why can requests and responses deadlock each other, even on a link that never drops anything?

The obvious answer, and why it breaks

The obvious view is that a lossless link with correct flow control cannot deadlock: every message eventually finds room. That is true for messages that are independent. Requests and responses are not: a node can only finish with a request by producing a response. That creates a dependency between message types, and if both types share a buffer, the dependency can close a cycle, even when routing itself is deadlock-free. This is message-dependent deadlock.

The idea: requests depend on responses

The cycle: A's buffer is full of B's requests → A cannot remove them until it sends responses → responses need room in B's buffer → B's buffer is full of A's requests → B cannot remove them until it sends responses → which need room in A's buffer. The fix removes one edge: give responses their own buffer, and make every node always accept responses, which it can, because consuming a response needs nothing else.

Build it: a model that deadlocks, then does not

This is DCLink step 8. Two nodes each want to send 6 requests; each request must be answered. Each node first sends as many requests as fit, then serves one request if the response fits. Every node has 4 receive slots in all three runs, so only the way they are shared changes: freely shared, split into two physical 2-slot buffers, or one buffer in which requests may hold at most 2 slots:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

"""Message-dependent deadlock between two nodes (DCLink step 8).

Nodes A and B each send requests to the other and must answer every request they
receive with a response. Each node has a receive buffer of 4 slots in every mode, so
the comparison is at equal total capacity. Each cycle a node first sends as many new
requests as the other node will accept, then takes in one response it holds, then
tries to serve one request it holds, which needs room for the response at the other node.
  shared:    requests and responses compete for all 4 slots
  separate:  2 slots for requests and 2 for responses, as two physical buffers
  reserved:  one 4-slot buffer, but requests may occupy at most 2 slots, so 2 are
             always kept for responses (shared storage with protected capacity)
In the last two, a node always accepts responses when they fit in the response share,
because a response only finishes a transaction and needs nothing further.
"""

SLOTS, REQ_MAX = 4, 2


def run(mode, requests=6, cycles=200):
    to_send = {"A": requests, "B": requests}
    buf = {"A": [], "B": []}                 # receive buffer at each node: "req" / "rsp"
    done = {"A": 0, "B": 0}
    other = {"A": "B", "B": "A"}

    def room(n, kind):                       # may node n accept one more message of this kind?
        reqs, rsps = buf[n].count("req"), buf[n].count("rsp")
        if mode == "shared":
            return reqs + rsps < SLOTS
        share = REQ_MAX if kind == "req" else SLOTS - REQ_MAX
        return (reqs if kind == "req" else rsps) < share   # separate and reserved behave alike

    for t in range(cycles):
        progress = False
        for n in ("A", "B"):                 # both send greedily first
            o = other[n]
            while to_send[n] and room(o, "req"):
                buf[o].append("req"); to_send[n] -= 1; progress = True
        for n in ("A", "B"):
            o = other[n]
            if "rsp" in buf[n]:              # a response finishes a transaction
                buf[n].remove("rsp"); done[n] += 1; progress = True
            if "req" in buf[n] and room(o, "rsp"):   # serve a request if the response fits
                buf[n].remove("req"); buf[o].append("rsp"); progress = True
        if not progress or done["A"] == done["B"] == requests:
            return t, done
    return cycles, done


results = {}
for mode in ("shared", "separate", "reserved"):
    t, done = run(mode)
    results[mode] = done
    stuck = " (stuck: both buffers full of requests)" if done["A"] < 6 else ""
    print(f"{mode:9s} 4 slots per node: completed A {done['A']}, B {done['B']} of 6 by cycle {t}{stuck}")
assert results["shared"]["A"] < 6
assert results["separate"] == results["reserved"] == {"A": 6, "B": 6}
print("PASS: with the same 4 slots, sharing them freely deadlocks; keeping room for responses, in a separate buffer or as a reserved share, always completes")

It prints:

shared    4 slots per node: completed A 0, B 0 of 6 by cycle 1 (stuck: both buffers full of requests)
separate  4 slots per node: completed A 6, B 6 of 6 by cycle 6
reserved  4 slots per node: completed A 6, B 6 of 6 by cycle 6
PASS: with the same 4 slots, sharing them freely deadlocks; keeping room for responses, in a separate buffer or as a reserved share, always completes

With freely shared slots, both buffers fill with requests in the first cycle and nothing more happens: neither node can send a response. With the same 4 slots split, or with 2 of them reserved for responses, both nodes finish all six by cycle 6. No slot was added; what changed is that requests can no longer take the space their own responses need. The two working versions behave identically here: what matters is the guarantee, not whether the storage is physically separate.

The general rule

• One class per dependency level. If handling message type X can require sending type Y, X must never be able to take the space Y needs, anywhere on the path. Requests and responses are two levels; coherence protocols often have three or more (requests, snoops, snoop responses, data).

• The last level must always be consumed. The final message type in a chain (responses, completions) must be accepted unconditionally by its destination (lesson 9.5).

• Separate means guaranteed everywhere: on every link, router and bridge the response class needs space and credits that requests cannot take, and a way to move that does not wait behind blocked requests. That can be physically separate buffers and virtual channels, or shared storage with a reserved minimum per class and separate credit counts; a shared queue in which a response can sit behind a stuck request is not enough.

How real protocols chose

What breaks

The opening link (illustrative) had been tested with traffic in one direction at a time, where a single shared buffer per end works fine. Only bidirectional bursts filled both ends with requests at once. Splitting each end's buffer into request and completion parts, with completions always accepted, removed the deadlock without adding any buffer space: the same slots, with half of them kept for completions.

Key takeaways

• Requests depend on responses: a node finishes a request only by sending a response.

• Shared buffers let a burst of requests block the responses they need: message-dependent deadlock.

• Guarantee each message class space it can always use, end to end (separate buffers or a reserved share), and always consume the last class in each chain.

Related topics

• Part 9 overview: Deadlock and Liveness