The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels

Yishay Mansour, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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 n messages that uses less than n headers cannot be bounded by any function of 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 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.

Original languageEnglish (US)
Pages (from-to)783-799
Number of pages17
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Jan 10 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • data link
  • lower bound
  • non-FIFO channels
  • sequence transmission

Cite this