Ordering and timeliness requirements of dependable real-time programs

Paulo Veríssimo

in Journal of Real-Time Systems, Kluwer Eds., (7):105-128, 1994.

Abstract

It is significantly difficult to program dependable decentralised computer control systems, since they need to integrate fault-tolerance and real-time with distribution. In consequence, architects and programmers turn to new distributed system tools and paradigms, such as: synchronised clocks, causal order, groups, membership, replication, and so forth, to assist them in that task. Their inappropriate use, however, may lead to unexpected inefficiency or failure of programs. There is a common link between all these tools in real-time uses, and that is the role of time and order in the behaviour of the system.

The purpose of this paper is to establish the limits to their use, in order that the models programmers rely on are not used beyond their validity boundaries. This paper equates the time and order problems of real-time programs in a unified manner. It recalls known fundamental limits of time and order in distributed systems, and then it shows that these limits can be drastically relaxed, if the system support (clock granularity, order discrimination) can be matched to the ordering and timeliness requirements of programs. It finalises by giving concrete guidelines about the use of clocks and about what a programmer can expect from an ordering by distributed timestamps.

Also available as INESC AR/14-94 (gzip postscript).