The Data Link Layer: Two Impossibility Results

Abstract

The data link layer in a layered communication network is designed to ensure reliable data transfer over a noisy physical channel. Formal specifications are given for physical channels and data links, in terms of I/O automata. Based on these specifications, two impossibility results are proved. First, no data link protocol can tolerate crashes of the host processors on which the protocol runs. Second, any data link protocol constructed to use an arbitrary non-FIFO physical channel requires unbounded headers. Keywords: Crashing; Volatile memory bounded headers; Communication protocols; Data link layer; Physical layer.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1988
Accession Number
ADA200983

Entities

People

  • Alan Fekete
  • Nancy Lynch
  • Yishay Mansour

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Autonomy
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automata
  • Classification
  • Communication Networks
  • Computer Science
  • Computers
  • Contracts
  • Data Links
  • Data Transmission
  • Electric Vehicles
  • Massachusetts
  • Notation
  • Security
  • Specifications
  • Transmitters
  • Transmitting

Readers

  • Fluid Dynamics.
  • Parallel and Distributed Computing.
  • Radio communications and signal processing.