Approximate Causal Observer

Sandeep S. Kulkarni and Mahesh Arumugam


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. However, 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 sensor networks that provide simple guarantees about the clock drift among sensors and about maximum delay of messages that are not lost. Our solution lets the sensors 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 our solution provides a continuum where the application can choose the size of the timestamps it maintains by identifying the level of causality violations it can tolerate.


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