Probabilistic analysis of causal message ordering

Causal message ordering (CMO) demands that messages directed to the same destinations must be delivered in an order consistent with their potential causality. In this paper, we present a modular decomposition of CMO, and evaluate the probability of breaking CMO by assuming two probabilistic models on message delays: exponential distribution and uniform distribution. These models represent the contexts where message delays are unpredictable and, respectively, unbounded and bounded. Our analysis results help in understanding the necessity of CMO schemes, and suggest a probabilistic approach to CMO: deferred sending. The effect of deferred sending is analyzed.