Deadline-Constrained Causal Order

L. Rodrigues, R. Baldoni, E. Anceaume, M. Raynal

Selected sections of this report will be published in the Proceedings of the 3rd IEEE International Symposium on Object-oriented Real-time distributed Computing, Newport Beach, California, USA, March, 2000.


A causal ordering protocol ensures that if two messages are causally related and have the same destination, they are delivered to the application in their sending order. Causal order strongly simplifies the development of distributed object-oriented systems. To prevent causal order violation, either messages may be forced to wait for messages in their past, or late messages may have to be discarded. For a real-time setting, the first approach is not suitable since when a message misses a deadline, all the messages that causally depend on it may also be forced to miss their deadlines. We propose a novel causal ordering abstraction that takes messages deadlines into consideration. Two implementations are proposed in the context of multicast and broadcast communication that delivers as many messages as possible to the application. Examples of distributed soft real-time applications that benefit from the use of a deadline-constrained causal ordering primitive are given. Also available extended report (gzip postscript), (pdf) .
Luís Rodrigues