### The intractability of bounded protocols for on-line sequence transmission over non-FIFO channelsThe intractability of bounded protocols for on-line sequence transmission over non-FIFO channels

Access Restriction
Subscribed

 Author Mansour, Yishay ♦ Schieber, Baruch Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Data link ♦ Lower bound ♦ Non-FIFO channels ♦ Sequence transmission Abstract The efficiency of data-link protocols for reliable transmission of a sequence of messages over non-FIFO physical channels is discussed. The transmission has to be on-line; i.e., a message cannot be accessed by the transmitting station before the preceding message has been received. Three resources are considered: The number of packets that have to be sent, the number of headers, and the amount of space required by the protocol. Three lower bounds are proved. First, the space required by any protocol for delivering $\textit{n}$ messages that uses less than $\textit{n}$ headers cannot be bounded by any function of $\textit{n}.$ Second, the number of packets that have to be sent by any protocol that uses a fixed number of headers in order to deliver a message is linear in the number of packets that are delayed on the channel at the time the message is sent. Finally, the notion of a probabilistic physical channel, in which a packet can be delayed on the channel with probability $\textit{q},$ is introduced. An exponential lower bound, with overwhelming probability, is proved on the number of packets that have to be sent by any data-link protocol using a fixed number of headers when it is implemented over a probabilistic physical channel. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 4 Page Count 17 Starting Page 783 Ending Page 799

#### Open content in new tab

Source: ACM Digital Library