The Need for Headers: An Impossibility Result for Communication over Unreliable Channels

Abstract

It is proved that any protocol that constructs a reliable data link service using a physical channel service necessarily includes in the packets some header information that enables the protocol to treat different packets differently. The physical channel considered is permitted to lose, but not reorder or duplicate packets. The formal framework used for the proof is the input/output automation model.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA222823

Entities

People

  • Alan Fekete
  • Nancy Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Alphabets
  • Automata
  • Classification
  • Computer Science
  • Computers
  • Construction
  • Data Links
  • Information Processing
  • Information Systems
  • Machines
  • Military Research
  • Security
  • Sequences
  • Specifications
  • Transmitting

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Logistics and Supply Chain Management.
  • Theoretical Analysis.