CONNECTION MANAGEMENT WITHOUT RETAINING INFORMATION

Managing a connection between two hosts in a network is an important s ervice to provide in order to make the network useful for many applica tions. The two main subproblems are the management of serial incarnati ons of a connection and the transfer of messages within an incarnation , This paper investigates whether it is necessary for connection manag ement protocols to retain state information across node crashes and be tween incarnations. The following results were obtained: When informat ion is not retained across node crashes, incarnation management is not possible at all. When information is not retained between incarnation s, incarnation management is possible if the network is FIFO and not p ossible if the network is non-FIFO. When information is not retained a cross node crashes, message transfer can be accomplished in networks t hat 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 de liver messages. However, message transfer cannot be accomplished if th e network is non-FIFO or the grace period allowed is fixed. When infor mation is not retained across node crashes, message transfer can he ac complished in networks that do not lose packets if the network is FIFO or the protocol need not be FIFO, Message transfer is not possible wh en the network is non-FIFO and the protocol must be FIFO. If the netwo rk has bounded capacity, then message transfer possible without using stable storage. This indicates, somewhat surprisingly, that there is a data link initialization protocol that can withstand node crashes wit hout stable storage. (C) 1995 Academic Press, Inc.