Replica determinism and flexible scheduling in hard real-time dependable systems

Citation
S. Poledna et al., Replica determinism and flexible scheduling in hard real-time dependable systems, IEEE COMPUT, 49(2), 2000, pp. 100-111
Citations number
34
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON COMPUTERS
ISSN journal
00189340 → ACNP
Volume
49
Issue
2
Year of publication
2000
Pages
100 - 111
Database
ISI
SICI code
0018-9340(200002)49:2<100:RDAFSI>2.0.ZU;2-M
Abstract
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.