×

Trade-off results for connection management. (English) Zbl 1008.68010

Summary: 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.

MSC:

68M12 Network protocols
68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afek, Y.; Attiya, H.; Fekete, A.; Fischer, M.; Lynch, N.; Mansour, Y.; Wang, D.-W.; Zuck, L., Reliable communication over unreliable channels, J. ACM, 41, 6, 1267-1297 (1994)
[2] Attiya, H.; Dolev, S.; Welch, J. L., Connection management without retaining information, Inform. Comput., 123, 2, 175-191 (1995) · Zbl 0839.68004
[3] Attiya, H.; Herzberg, A.; Rajsbaum, S., Optimal clock synchronization under different delay assumptions, SIAM J. Comput., 25, 2, 369-389 (1996) · Zbl 0844.68043
[4] Attiya, H.; Rappoport, R., The level of handshake required for establishing a connection, (Tel, G.; Vitanyi, P., Proc. 8th Internat. Workshop on Distributed Algorithms. Proc. 8th Internat. Workshop on Distributed Algorithms, Lecture Notes in Computer Science, vol. 857 (1994), Springer: Springer Berlin), 179-193
[5] Belsnes, D., Single-message communication, IEEE Trans. on Commun., 24, 2 (1976)
[6] Gawlick, R.; Segala, R.; Sogaard-Andersen, J.; Lynch, N., Liveness in timed and untimed systems, (Abiteboul, S.; Shamir, E., Proc. 21st Internat. Colloq. on Automata, Languages and Programming. Proc. 21st Internat. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 820 (1994), Springer-Verlag: Springer-Verlag Berlin), 166-177 · Zbl 0917.68152
[7] J. Kleinberg, H. Attiya, N. Lynch, Trade-offs between message delivery and quiesce times in connection management protocols, Proc. 3rd Israel Symp. on the Theory of Computing and Systems, January 1995, pp. 258-267.; J. Kleinberg, H. Attiya, N. Lynch, Trade-offs between message delivery and quiesce times in connection management protocols, Proc. 3rd Israel Symp. on the Theory of Computing and Systems, January 1995, pp. 258-267.
[8] Liskov, B.; Shrira, L.; Wroclawski, J., Efficient at-most-once messages based on synchronized clocks, ACM Trans. Comput. Systems, 9, 2, 125-142 (1991)
[9] Lundelius, J.; Lynch, N., An upper and lower bound for clock synchronization, Inform. Control, \(62, 2/3, 190-204 (1984)\) · Zbl 0591.68023
[10] Lynch, N.; Tuttle, M., An introduction to input/Output automata, CWI Quart., 2, 3, 219-246 (1989) · Zbl 0677.68067
[11] Lynch, N.; Vaandrager, F., Forward and backward simulations for timing-based systems, (de Bakker, J. W.; Huizing, C.; de Roever, W. P.; Rozenberg, G., Real-TimeTheory in Practice. Real-TimeTheory in Practice, Lecture Notes in Computer Science, Vol. 600 (1991), Springer-Verlag: Springer-Verlag Berlin), 397-446
[12] N. Lynch, F. Vaandrager, Forward and backward simulations—Part II: timing-based systems, Technical Memo MIT/LCS/TM-487.b, Laboratory for Computer Science, Massachusetts Institute of Technology, September 1993.; N. Lynch, F. Vaandrager, Forward and backward simulations—Part II: timing-based systems, Technical Memo MIT/LCS/TM-487.b, Laboratory for Computer Science, Massachusetts Institute of Technology, September 1993. · Zbl 0856.68103
[13] Patt-Shamir, B.; Rajsbaum, S., A theory of clock synchronization, Proc. 26th Ann. ACM Symp. on Theory of Computing, 810-819 (1994) · Zbl 1344.68034
[14] Stevens, R. W., TCP/IP Illustrated, Vol. 1: The Protocols (1994), Addison-Wesley Professional Computing Series: Addison-Wesley Professional Computing Series Reading, MA
[15] Sunshine, C.; Dalal, Y., Connection management in transport protocols, Computer Networks, 2, 454-473 (1978)
[16] Tanenbaum, A., Computer Networks (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[17] Tomlinson, R., Selecting sequence numbers, ACM Oper. Systems Rev., 3 (1975)
[18] Transmission Control Protocol, DARPA Network Working Group Report RFC-793, University of Southern California, September 1981.; Transmission Control Protocol, DARPA Network Working Group Report RFC-793, University of Southern California, September 1981.
[19] Watson, R. W., Timer-based mechanisms in reliable transport protocol connection management, Comput. Networks, 5, 47-56 (1981)
[20] Watson, R. W., The Delta-t transport protocol: features and experience, Proc. IEEE Internat. Conf. on Local Computer Networks, 399-407 (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.