Approximate Causal Observer

Sandeep S. Kulkarni and Mahesh Arumugam

Abstract

In this paper, we focus on the problem of approximate causal delivery. This problem identifies the tradeoff between causal delivery and timely delivery of messages. Causal delivery requires that delivery of a message, say $m$, be delayed until all messages on whom $m$ is causally dependent are delivered. By contrast, timely delivery requires that messages be delivered as soon as possible. In the context where messages could be lost and the {\em value} of messages decreases as the delay increases, the requirements of causal delivery and timely delivery are conflicting.

We show how a simple logical timestamp program can be used to obtain a solution for approximate causal observer. This solution is intended for systems that provide simple guarantees about the clock drift and about maximum delay of messages that are not lost. While $O (n^2)$ {\em unbounded} integers are required to implement {\em perfect} causal delivery, our solution uses only $O (log \ n)$ {\em bounded} space. Our solution permits a process to tradeoff between causal delivery and timely delivery, i.e., it allows the process to choose the level of causality violations it can tolerate ($0\%$ or more) and the time for which it will have to buffer the received messages. We also show that the information maintained by our program, although small, is important to provide such a tradeoff; we show that the number of causality violations increase by an order of magnitude if this information is not maintained. Finally, we show how our solution can be used to observe computations in sensor networks while providing a continuum where one can choose the size of the timestamps based on the acceptable level of causality violations.

Paper:

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