View Related Documents

Abstract

The famous alternating bit protocol is an algorithm for transmitting a sequence of data through a so-called faulty channel, i.e. a channel that can lose or duplicate injected data. The established literature provides a wealth of treatments and plenty of a-posteriori correctness proofs of the protocol; derivations of the algorithm, however, are very rare. The prime purpose of this note is to provide such a derivation from first principles, using the theory of Owicki and Gries as the only tool for reasoning about parallel programs.

Keywords  Program derivation - multiprogramming - the theory of Owicki and Gries - multibounds - faulty channels - the alternating bit protocol

Fulltext Preview

Image of the first page of the fulltext document