Real-time causal message ordering in multimedia systems

Abstract

In multimedia systems, not only do messages that are sent to and received by multiple sites need to have a consistent order imposed by all sites, but cause and effect relations must be maintained. Causal ordering allows the cause and effect relations of messages to be maintained. This paper presents an algorithm that insures that multimedia data with real-time deadlines are delivered to the application layer in causal order. The algorithm is designed to insure that any message that arrives at a destination site before its deadline will be delivered to the application before the message expires. In addition, by focusing on a form of causal ordering violations caused by "the triangle inequality," this algorithm has a low overhead with respect to the amount of information that must be appended to each message.