Trade-off results for connection management

Abstract

A connection management protocol establishes and handles a connection between two hosts across a wide-area network to allow reliable message delivery. We continue the previous work of Kleinberg et al. (Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems, January (1995), pp. 258-267) to study the precise impact of the level of synchrony provided by the processors' clocks on the performance of connection management protocols, under common assumptions on the pattern of failures of the network and the host nodes. Two basic timing models are assumed: clocks that exhibit a certain kind of a drift from the rate of real time, and clocks that display a pattern of synchronization to real time. We consider networks that can duplicate and reorder messages, and nodes that can crash. We are interested in simultaneously optimizing the following performance parameters: the message delivery time, which is the time required to deliver a message, and the quiescence time, which is the time that elapses between periods of quiescence, in which the receiving host deletes all earlier connection records and returns to an initial state. We establish natural trade-offs between message delivery time and quiescence time, in the form of tight lower and upper bounds, for each combination of the timing models and failure types. Several of our trade-off results significantly improve upon or extend previous ones shown by Kleinberg et al. © 2002 Elsevier Science B.V. All rights reserved.