Transmission Control Protocol (TCP)

Stulp & Verbrugge (2005) presented a knowledge based algorithm for the Transmission Control Protocol (TCP). TCP aims to solve the sequence transmission problem.

The sequence transmission problem lies at the heart of epistemic analyses of transmission protocols. This is the problem of transmitting an infinite sequence of messages from a sender S to a receiver R over a channel that can contain (in our case) both reordering and deletion errors. Halpern and Zuck (1992) state the problem as follows:

"Consider two processes, called the sender and the receiver. The sender S has an input tape with an infinite sequence X = <x0,x_1,..> of data elements. S reads these data elements and tries to transmit them to the receiver R. R must write these data elements onto an output tape. We require that (a) at any time the sequence of data elements written by R is a prefix of X (this is the safety property) and (b) if the communication medium satisfies appropriate fairness conditions, then every data element xi in the sequence X is eventually written by R (this is the liveness property)."

Furthermore, Halpern and Zuck provide a framework for analyzing transmission protocols. They define a knowledge-based protocol as a program written in a high-level programming language. All existing protocols can be seen as implementations of the knowledge-based protocol underlying it. In the knowledge-based framework, the robustness of all transmission protocols can be analyzed in a similar, uniform fashion. The following questions can then be studied with respect to the analyzed algorithm (Stulp and Verbrugge, 2002):

"Can mutation, deletion or insertion errors be handled by this protocol? If not, what are the practical consequences? How much knowledge can the protocol attain about delivered data?"

Whereas Halpern and Zuck performed and epistemic analysis of a great number of theoretical protocols, Stulp and Verbrugge (2002) provided a knowledge-based approach to, allegedly, the most famous and most implemented transmission protocol: the Transmission Control Protocol (TCP). They proved the protocol guarantees safety and liveness when any two kinds of deletion, mutation and insertion errors occur. They also proved that the sender and the receiver using TCP can acquire depth n knowledge about the values of the messages for any n.

A simulation of the knowledge-based algorithm describing the Transmission Control Protocol can be found here.