A causal message ordering scheme for distributed embedded real-time systems

In any distributed system, messages must be ordered according to their cause-and-effect relation to ensure correct behavior of the system. Causal ordering is also essential for services like atomic multicast and replication. In distributed real-time systems, not only must proper causal ordering be ensured, but message deadlines must be met as well. Previous algorithms which ensure such behavior include the Δ-protocol family and the MARS approach. However, both these algorithms give large response times by delaying all messages for a fixed period of time. In this paper we show that for small- to medium-sized real-time systems (consisting of a few tens of nodes) as are commonly used for embedded applications, it becomes feasible to extend the h-protocol so that instead of delaying all messages for a fixed period, each message is delayed according to its deadline. Our algorithm requires certain message deadlines to be adjusted by the application designer and we show that for small-scale applications such as those used in embedded systems, this adjustment is feasible and can be automated by the use of proper CAD tools