NDLI: The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels

Content Provider	ACM Digital Library
Author	Mansour, Yishay Schieber, Baruch
Copyright Year	1992
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.
Starting Page	783
Ending Page	799
Page Count	17
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/146585.146596
Journal	Journal of the ACM (JACM)
Volume Number	39
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-10-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Data link Lower bound Non-FIFO channels Sequence transmission
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Recoverable sequence transmission protocols

Online tracking of mobile users

Reliable communication over unreliable channels

A Lower Bound to Finding Convex Hulls

The intractability of bounded protocols for non-FIFO channels

Lower Bounds and Fast Algorithms for Sequence Acceleration

A Unified Lower Bound for Selection and Set Partitioning Problems

A Lower Bound on the Complexity of Orthogonal Range Queries

Optimal Rate Code Constructions for Computationally Simple Channels

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

Similar Documents

Recoverable sequence transmission protocols

Online tracking of mobile users

Reliable communication over unreliable channels

A Lower Bound to Finding Convex Hulls

The intractability of bounded protocols for non-FIFO channels

Lower Bounds and Fast Algorithms for Sequence Acceleration

A Unified Lower Bound for Selection and Set Partitioning Problems

A Lower Bound on the Complexity of Orthogonal Range Queries

Optimal Rate Code Constructions for Computationally Simple Channels

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