Stabilizing Causal Deterministic Merge

Sandeep S. Kulkarni, Ravikant 

Abstract

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

BibTeX Entry

@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 =    {} }


Return to the publication list
Return to the Sandeep's home page