On Lamport's interprocessor communication model

Abstract
Leslie Lamport presented a set of axioms in 1979 that capture the essential properties of the temporal relationships between complex and perhaps unspecified activities within any system, and proceeded to use this axiom system to prove the correctness of sophisticated algorithms for reliable communication and mutual exclusion in systems without shared memory. As a step toward a more complete metatheory of Lamport's axiom system, this paper determines the extent to which that system differs from systems based on “atomic,” or indivisible, actions. Theorem 1 shows that only very weak conditions need be satisfied in addition to the given axioms to guarantee the existence of an atomic “model,” while Proposition 1 gives sufficient conditions under which any such model must be a “faithful” representation. Finally, Theorem 2 restates a result of Lamport showing exactly when a system can be thought of as made up of a set of atomic events that can be totally ordered temporally. A new constructive proof is offered for this result.

This publication has 11 references indexed in Scilit: