TY - GEN

T1 - Intractability of bounded protocols for non-FIFO channels

AU - Mansour, Yishay

AU - Schieber, Baruch

PY - 1989

Y1 - 1989

N2 - We discuss the efficiency of data link protocols for non-FIFO physical channels. We consider three resources; the number of packets that have to be sent, the number of headers, and the amount of space required by the protocol. We prove three lower bounds. First, we show that the space required by any protocol for delivering n messages using less than n headers can not be bounded by any function of n. Second, we prove that the number of packets that have to be sent by any data link protocol using 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, we introduce the notion of a probabilistic physical channel, in which a packet is lost with probability q. We prove an exponential lower bound, with overwhelming probability, 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.

AB - We discuss the efficiency of data link protocols for non-FIFO physical channels. We consider three resources; the number of packets that have to be sent, the number of headers, and the amount of space required by the protocol. We prove three lower bounds. First, we show that the space required by any protocol for delivering n messages using less than n headers can not be bounded by any function of n. Second, we prove that the number of packets that have to be sent by any data link protocol using 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, we introduce the notion of a probabilistic physical channel, in which a packet is lost with probability q. We prove an exponential lower bound, with overwhelming probability, 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.

UR - http://www.scopus.com/inward/record.url?scp=0024931994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024931994&partnerID=8YFLogxK

U2 - 10.1145/72981.72985

DO - 10.1145/72981.72985

M3 - Conference contribution

AN - SCOPUS:0024931994

SN - 0897913264

SN - 9780897913263

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 59

EP - 72

BT - Proc Eighth ACM Symp Princ Distrib Comput

PB - Publ by ACM

T2 - Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing

Y2 - 14 August 1989 through 16 August 1989

ER -