On equivalence-completions of fairness assumptions

Abstract

Abstract The paper considers the treatment of fairness assumptions which are not equivalence-robust , a central issue in relating interleaving semantics to partial order semantics . A notion of completion is introduced and studied, and two specific completions are considered: maximal completion , which is easier to implement (shown by a broadcast bus implementation) but guarantees only weak liveness properties of programs using it; and minimal completion , which may be harder to implement but induces stronger liveness properties on programs using it. Some properties of completions are formulated. Finally, the impact of non-equivalence-robustness on compositionality with respect to separate fairness assumptions is considered.