Possible Deadlock in ICP
A deadlock hazard when two hosts initialize a connection
Wolfe, S.M. and J. Postel, "Possible Deadlock in ICP", RFC 202, DOI 10.17487/RFC0202, July 1971, <https://www.rfc-editor.org/info/rfc202>.
@misc{rfc202,
series = {Request for Comments},
number = 202,
howpublished = {RFC 202},
publisher = {RFC Editor},
doi = {10.17487/RFC0202},
url = {https://www.rfc-editor.org/info/rfc202},
author = {S.M. Wolfe and J. Postel},
title = {{Possible Deadlock in ICP}},
pagetotal = 2,
year = 1971,
month = jul,
} RFC text
Network Working Group Steve Wolfe
Request for Comments: #202 UCLA-CCN
NIC #7155 Jon Postel
Categories: D UCLA-NMC
References: Document #2 26 July 1971
Obsoletes: None
We have noticed a possible deadlock situation which may arise using the
Initial Connection Protocol (ICP) specified in Document #2 (NIC #7101 in
the Current Network Protocols Notebook NIC #7104).
If on both sides one RFC is issued and a "wait for match" is required
before the second RFC is issued, it is possible that the first RFC's
will not match. In particular a deadlock will occur if both sides open
their send or both sides open their receive sockets first.
Briefly the ICP is:
<where the original uses a script lowercase letter with a single digit
subscript we use the lower case letter followed by {digit} so that
script-m-subscript-2 is printed m{2}>
Server User
------ ----
S1: Listen on socket L. U1: RTS(U, L, l{1})
S2: Wait for a match. U2: Wait for match.
S3: STR(L, U, s{1})
S4: Wait for allocation. U3: All(l{1}, m{1}, b{1})
S5: Send data S in s{1} bit U4: Receive data S in s{1}
bytes as allowed by bit bytes.
allocation m{1}, b{1}.
S6: CLS(L, U) U5: CLS(U, L)
S7: RTS(S, U+3, l{2}) U6: STR(U+3, S, s{2})
S8: STR(S+1, U+2, s{3}) U7: RTS(U+2, S+1, l{3})
"The labels here imply no ordering except that ordering required by the
Host-Host Protocol. Note that steps S7 and S8 can be reversed as can U6
and U7. Also, notice that at any time after S2 the server could
initiate steps S7 and S8 in parallel with steps S3 through S6, and that
at any time after U4 the user could initiate steps U6 and U7 in parallel
with step U5."
We recommend that the server perform steps 7 and 8 before waiting for
the user to perform step 6 or 7. It is also suggested that the user
issue the RFC's in steps 6 and 7 without waiting for the server. (If
the user is only Listening then both Listens should be issued without
waiting for the server.) If for some reason a host must delay between
issuing RFC's it must issue the RFC's involving sockets S and U+3 first.
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Robert Barnes 6/97 ]
AI ELI5
On this page
§1The Deadlock
The Initial Connection Protocol specifies handshake steps for a server and user to connect. If both sides issue one request for comment (RFC) and wait for it to be acknowledged before issuing a second, deadlock is possible. In particular, if both sides attempt to open their send sockets first, or both attempt to open their receive sockets first, the first RFCs will not match and the connection hangs.
If both sides do exactly the same thing in the same order, they can get stuck waiting for each other.
§2The Solution
RFC 202 recommends two changes: First, the server should perform its open-socket steps before waiting for a user response. Second, the user should issue its RFCs in sequence without waiting for the server to reply to each one. Additionally, if a host must delay between RFCs, it should prioritize issuing the ones on sockets S and U+3 first, as these are critical for breaking the deadlock.
The server goes first and does not wait; the user sends all its requests quickly. This way neither side gets stuck.
§3Implications
This errata clarified a subtle race condition in the ICP that could trap implementations in mutual waiting. By ensuring one side takes initiative and the other side batches its requests, the protocol could proceed reliably. The fix shows that connection setup protocols must carefully order operations to avoid deadlock, a lesson that became central to later transport protocol design.
Taking turns and not waiting too long keeps things moving. This idea showed up in later connection setup rules.