Need for Headers: An Impossibility Result for Communication over UnreliableChannels

摘要

It is proved that any protocol that constructs a reliable data link service usinga 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 moded. Keywords: Concurrent programming.