Accession Number:

ADA200983

Title:

The Data Link Layer: Two Impossibility Results

Descriptive Note:

Technical memo.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Report Date:

1988-05-01

Pagination or Media Count:

25.0

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 IO 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.

Subject Categories:

  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE