ALCOMFT-TR-01-9

M. Adler, F. Fich, L. A. Goldberg and M. Paterson
Tight Size Bounds for Packet Headers in Narrow Meshes
Warwick. Work package 2. January 2001.

Abstract: Consider the problem of sending a single message from a sender to a receiver through an mx n mesh with asynchronous links that may stop working, and memoryless intermediate nodes. We prove that for m\in O(1), it is necessary and sufficient to use packet headers that are Theta( log log n) bits long.

Postscript file: ALCOMFT-TR-01-9.ps.gz (97 kb).