In this paper, we present a causal deterministic merge program for publish-subscribe systems. Our program ensures that if two subscribers receive two messages then they receive them in the same order. Also, it guarantees that the order in which a subscriber receives messages is a linearization of the causal order among those messages. To develop our program, we expect two guarantees from the underlying system: the first guarantee deals with the difference between physical clocks and the second guarantee deals with message delays. While $O(n^2)$ space is required for causal deterministic merge in asynchronous systems, our program only uses $O(log \ n)$ space. We also show how our program can be made stabilizing while using only a bounded space. And, the recovery time for our program is proportional to the guarantees made by the underlying system.
Paper:
Slides@Article{ftrtft2000,
author = {S.~S.~Kulkarni and Ravikant},
title = {Stabilizing Causal Deterministic Merge},
journal = {Workshop on Self-stabilization},
year = {2001},
OPTkey = {},
OPTvolume = {},
OPTnumber = {},
OPTpages = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {} }