Evaluation of the Optimal Causal Message Ordering Algorithm

摘要

An optimal causal message ordering algorithm was recently proposed by Kshemkalyani and Singhal, and its optimality was proved theoretically. For a system of n processes, although the space complexity of this algorithm was shown to be O(n~2) integers, it was expected that the actual space overhead would be much less than n~2. In this paper, we determine the overhead of the optimal causal message ordering algorithm via simulation under a wide range of system conditions. The optimal algorithm is seen to display significantly less message overhead and log space overhead than the canonical Raynal-Schiper-Toueg algorithm.