Distributed Algorithms

Chapter 22 Data Link Protocols

In this chapter, we consider the problem of implementing reliable FIFO communication using less reliable channels. This is one of the most fundamental problems solved by communication networks. The "less reliable channels" we consider include channels that exhibit failures such as the loss and duplication of messages, as well as channels that reorder messages. We also consider process crashes that lose process state information. We only consider the problem in the very special case of a two-node network.

We begin by presenting two simple, well-known algorithms: StenninG′s protocol and the Alternating Bit protocol. In Stenning’s protocol, the process at the sending end attaches (unbounded) integer tags to messages ...