Abstract
Causal order states that for any process the order in which it is delivered messages cannot violate the happened-before relation of the corresponding sendings. Such a communication abstraction has been defined for reliable distributed systems in which data of application messages have unlimited time validity. In this paper we extend the notion of causal order to cope with unreliable communication networks in which messages have real-time delivery constraints. In particular, we assume that messages have a limited time validity, Δ, after which their data can no longer be used by the application, and that some of them can be lost by the communication network. This new abstraction, called Δ-causal order, requires to deliver as many messages as possible within their validity time in such a way that these deliveries respect causal order. Two efficient implementations are proposed in the case of one-to-one and broadcast communication. Examples of distributed multimedia real-time applications, in which scheduling messages deliveries respecting Δ-causal order is a crucial point for the quality of the service, are given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alagar, S. and Venkatesan, S. 1994. “An optimal algorithm for distributed snapshots with causal message ordering”, Information Processing Letters, vol 50, pp. 311–316.
Birman, K. and Joseph, T. 1987. “Reliable communication in the presence of failures”, ACM Transactions on Computer Systems, 5(1), pp. 47–76.
Birman, K., Schiper, A. and Stephenson, P. 1991. “Lightweight causal order and atomic group multicast”, ACM Transactions on Computer Systems, 9(3):282–314.
Cristian, F., Aghili, H., Strong, R. and Dolev, D. 1995. “Atomic Broadcast: From simple message diffusion to Byzantine agreement, Information and Computation, 118(1):158–179.
Ferrari, D. 1990. “Clients requirements for real-time communication services,” IEEE Communication Magazine, 65–72.
Gronemberg, S. and Marwood, D. 1994. “Real time groupware as a distributed system: concurrency control and its effect on the interface,” In Proceedings of ACM conference on Cooperative Support for Cooperative Work, ACM press, 207–217, 1994.
Gusella, R. and Zatti, S. 1989. “The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3BSD,” IEEE Transactions on Software Engineering, 15(7):847–853.
Houdoin, T. and Bonjour, D. 1994. “ATM and AAL layer issues concerning multimedia applications,” Annals of Telecommunications, 49(5):230–240.
Jeffay, K., Stone, D.L. and Smith, F.D. 1994. “Transport and display mechanisms for multimedia conferencing across packet switched networks,” Computer Networks, 26:1281–1304.
Kopetz, H. and Ochsenreiter, W. 1987. “Clock synchronization in distributed real-time systems,” IEEE Transactions on Computers, (8):933–940.
Kopetz, H. Andreas, D., Koza, C., Mulazzani, M., Schwabl, W., Sentft, C., and Zainlinger, R. 1989. “Distributed fault-tolerant real-time systems: the Mars approach,” IEEE Micro:25–41.
Lamport, L. 1978. “Time, clocks and the ordering of events in a distributed systems,” Communications of the ACM, 21(7):558–565.
Ravindran, K. and Bansal, V. 1993. “Delay compensation protocols for synchronization of multimedia data streams,” IEEE Transactions on Knowledge and Data Engineering, 5(4):574–589.
Raynal, M. Schiper, A. and Toueg, S. 1991. “The causal ordering abstraction and a simple way to implement it,” Information Processing Letters, 39:343–350.
Schlichting, R.D. and Schneider, F.B. 1983. “Fail-stop processors: an approach to designing fault-tolerant computing systems,” ACM Transactions on Computer Systems, 1(3):222–238.
Verissimo, P. 1994. “Ordering and timeliness requirements of dependable real-time programs,” Journal of Real-Time Systems, Kluwer Eds., 7:105–128.
Verissimo, P. 1995 “Causal delivery protocols in real-time systems: a generic model,” Technical Report INESCIST, Technical University of Lisboa. to appear in Journal of Real-Time Systems, Kluwer Eds.
Wakeman, I. 1993. “Packetized video: options for interaction between the user, the network and the codec,” The Computer Journal, 36(1):55–66.
Yavatkar, R. 1992. “MCP: a protocol for coordination and temporal synchronization in multimedia collaborative applications,” In Proceedings of the 12th IEEE International Conference on Distributed Computing Systems, IEEE press, 606–613.
Yavatkar, R. and Lakshman, K. 1994. “Communication support for distributed collaborative applications,” Multimedia Systems, 2: 74–88.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Baldoni, R., Mostefaoui, A. & Raynal, M. Causal delivery of messages with real-time data in unreliable networks. Real-Time Syst 10, 245–262 (1996). https://doi.org/10.1007/BF00383387
Issue Date:
DOI: https://doi.org/10.1007/BF00383387