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 ident ical order within a given time interval. Distributed scheduling of replicat ed tasks, however, violates this requirement if on-line scheduling, preempt ive scheduling, or scheduling of dissimilar replicated task sets is employe d. This problem of inconsistent task outputs has been solved previously by coordinating the decisions of the local schedulers such that replicated tas ks are executed in an identical order. Global coordination results either i n an extremely high communication effort to agree on each schedule decision or in an overly restrictive execution model where on-line scheduling, arbi trary preemptions, and nonidentically replicated task sets are not allowed. To overcome these restrictions, a new method, called timed messages, is in troduced. Timed messages guarantee deterministic operation by presenting co nsistent message versions to the replicated tasks. This approach is based o n simulated common knowledge and a sparse time base. Timed messages are ver y effective since they neither require communication between the local sche duler nor do they restrict usage of on-line flexible scheduling, preemption s and nonidentically replicated task sets.