A formal model of asynchronous communication and its use in mechanically verifying a biphase mark protocol

Abstract

We present a formal model of asynchronous communication between two digital hardware devices. The model takes the form of a function in the Boyer-Moore logic. The function transforms the signal stream generated by one processor into that consumed by an independently clocked processor, given the phases and rates of the two clocks and the communications delay. The model can be used quantitatively to derive concrete performance bounds on communications at ISO protocol level 1 (physical level). We use the model to show that an 18-bit/cell biphase mark protocol reliably sends messages of arbitrary length between two processors provided the ratio of the clock rates is within 5% of unity.