On the Correctness of Sliding Window Protocols

Abstract

In this note some struggles with the sliding window protocol and the special case known as the alternating bit protocol, are reported. We try to give a correctness proof, and discover that we cannot do so for one of the versions of the sliding window protocol. One may either require channels that satisfy stronger assumptions or, as we will do, adapt the protocol and stick to the weaker assumptions. The alternating bit protocol can be traced back to [Bartlett]. We have been unable to trace back the origins of the sliding window protocols; [Stenning] discusses one of the versions and lists networks using related protocols.