Replica Determinism and Flexible Scheduling in Hard Real-Time Dependable Systems

Fault-tolerant real-time systems are typically based on active replication where replicated entities are required to deliver their outputs in an identical order within a given time interval. Distributed scheduling of replicated tasks, however, violates this requirement if on-line scheduling, preemptive scheduling or scheduling of dissimilar replicated task sets is employed. This problem of inconsistent task outputs has been solved previously by co-ordinating the decisions of the local schedulers such that replicated tasks are executed in an identical order. Global co-ordination results either in an extremely high communication effort to agree on each schedule decision or in an overly restrictive execution model where on-line scheduling, arbitrary preemptions and non-identically replicated task sets are not allowed. To overcome these restrictions, a new method, called timed messages, is introduced. Timed messages guarantee deterministic operation by presenting consistent message versions to the replicated tasks. This approach is based on simulated common knowledge and a sparse time base. Timed message are very effective since they neither require communication between the local scheduler nor do they restrict usage of on-line flexible scheduling, preemptions and non-identically replicated task sets. Key words: Distributed real-time systems, fault-tolerance, distributed operating systems, replica determinism, distributed scheduling, flexible scheduling.