Distributed synchronization protocols ensure the temporal consistency of logical processes in a simulation. Conservative protocols insist that messages be processed in strict message arrival order. Kumar and Shorey prove that the message queues of a logical process will become unstable in all circumstances, requiring that messages be queued in unbounded store. Consequently, the performance of the distributed simulation must be constrained by interprocessor flow control.
This research paper proves a fundamental consideration that has shaped many conservative algorithms, notably Lubachevsky’s bounded lag, which limits the forward processing of distinct logical processes, and Chandy-Misra’s null messaging algorithm, which supports one-level message buffering. The proof is rigorous, if a little terse, and assumes the reader has a detailed knowledge of Markov chains. Sufficient references are supplied to allow evaluation of the proof from first principles. The paper, as the authors readily acknowledge, complements research undertaken by Shanker and Patuwo [1], who reached the same conclusions by heuristic reasoning.
Anyone who is particularly interested in the fundamental concepts of conservative simulation will be interested in this useful paper. Its brevity may leave the reader wishing for a more thorough exploration of the themes of the paper.