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) .