Hagit Attiya, Shlomi Dolev and Jennifer L. Welch

Managing a connection between two hosts in a network is an important service to provide in order to make the network useful for many applications. The two main sub-problems are the management of serial incarnations of a connection and the transfer of messages within an incarnation. This paper investigates whether it is necessary for connection management protocols to retain state information across node crashes and between incarnations. The following results were obtained:

• When information is not retained across node crashes, incarnation management is not possible at all.
• When information is not retained between incarnations, incarnation management is possible if the network is FIFO and not possible if the network is non-FIFO.
• When information is not retained across node crashes, message transfer can be accomplished in networks that lose packets if the network is FIFO and the protocol is allowed a variable length grace period after a crash during which it need not deliver messages. However, message transfer cannot be accomplished if the network is non-FIFO or the grace period allowed is fixed.
• When information is not retained across node crashes, message transfer can be accomplished in networks that do not lose packets if the network is FIFO or the protocol need not be FIFO. Message transfer is not possible when the network is non-FIFO and the protocol must be FIFO.
• If the network has bounded capacity, then message transfer is possible without using stable storage. This indicates, somewhat surprisingly, that there is a data link initialization protocol that can withstand node crashes without stable storage.