Affiliations: Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA Tel.: +1 517 355 2387; Fax: +1 517 432 1061; E-mail: {sandeep, ravikant}@cse.msu.edu; Web: http://www.cse.msu.edu/˜{sandeep, ravikant}
Abstract: In this paper, we focus on causal deterministic merge – that combines causal delivery and uniform total order – in semi-synchronous publish-subscribe systems that provide simple guarantees related to clock values and message delays. We consider two properties of the timestamps used to obtain causal deterministic merge: (1) they should be bounded, i.e., for a given system, the maximum size of the timestamp should be independent of the length of the computation, and (2) they should be scalar, i.e., the time required to compare/update timestamps should be independent of the size of the system. By making certain assumptions about how the timestamps are compared, we show that it is impossible to obtain a solution that uses scalar and bounded timestamps. Hence, we focus on solutions that achieve one of these properties. We present two solutions where the size of the timestamps is bounded; the size of the timestamps in the first solution is logarithmic in the number of processes whereas in the second solution, it is linear in the number of processes. We also present a solution where the timestamp consists of O(1) integers that can grow unbounded; we further show that the timestamps in this solution can be bounded if the application provides a simple guarantee about event creation. Each of these solutions is stabilizing fault-tolerant in that even if the system is perturbed by faults that improperly initialize processes, lose/corrupt messages and temporarily violate system guarantees, the system recovers to states from where subsequent computation satisfies the requirements of causal deterministic merge. Our solutions improve previously known solutions in several ways: In previous solutions, the timestamps consist of O(n2) unbounded integers where n is the number of processes. By contrast, one of our solutions uses O(1) unbounded integers and the remaining three solutions use bounded integers.
