A NOTE ON LINEARIZABILITY AND THE GLOBAL TIME AXIOM
Bernadette Charron-Bost, Robert Cori · Parallel Processing Letters · 2003
The assumption of the existence of global time, which significantly simplifies the analysis of distributed systems, is generally safe since most of the conclusions obtained under the global time axiom can be transferred to the frame where no such assumption is made. In this note, we show that the compositionality of the well-known correctness condition for concurrent objects called linearizability does not satisfy this simplification rule: we present a simple non-linearizable system composed of two objects which are individually linearizable.