Abstract :
The causal order is central to many algorithms in both the message-passing and shared memory models. In the message-passing model, the causal order is clearly a strict, or irreflexive partial, order. However, some shared memory models are defined without reference to time. In those models, the causal order can fail to be a strict order. Existing works have either declared that all non-strict orders are not causal, or assumed that the causal order is strict without proof. We prove that, under a small number of reasonable assumptions about systems, the causal order is strict. In particular, we assume neither a global time model nor that processes issue a single shared memory operation at a time.
Keywords :
distributed algorithms; message passing; shared memory systems; causal order; distributed algorithm; message-passing model; shared memory model; strict order; Broadcasting; Conferences; Distributed computing; History; Intersymbol interference; Message passing; Middleware; Pipelines; Silicon compounds; US Government; Causal Order; Formal Verification;
