John Kleinberg, Hagit Attiya, and Nancy Lynch. Trade-offs between Message Delivery and Quiesce Times in Connection Management Protocols. Proceedings of the Third Israel Symposium on Theory of Computing and Systems, pages 258-267, Tel-Aviv, Israel, January 1995. .pdf

Abstract

The problem of implementing reliable message delivery using timing information is considered. Two important parameters, from the point of view of system performance, are the time required to deliver a message and the time that elapses between periods of quiescence, in which a processor returns to an initial state and deletes all earlier connection records. It has been frequently observed that there is no known protocol which simultaneously optimizes both these quantities; in this paper we prove such trade-offs precisely in the form of lower bounds. Despite the simple nature of the problem, the relationships among these lower bounds are quite subtle, in that they depend critically on the level of synchronization in the processors' clocks. We consider three basic timing models: asynchronous processors, processors which have (approximately) synchronized clocks, and processors with clocks that read different values but run at (approximately) the same rate. We mainly focus on networks that can duplicate and re-order packets; at the end, we also consider message loss and processor crashes.