21/1997 : Replica Determinism and Flexible Scheduling in Hard Real-Time Dependable Systems

RR Number

21/1997

Conference

IEEE Transactions on Computers, Vol. 49, No. 2, pp. 100-111, February 2000

Author(s)

Stefan Poledna, Peter Barrett, Alan Burns, Andy Wellings

Abstract

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. This global co-ordination -- based on group communication protocols -- 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. They allow the reduction of agreement and group communication protocols to the theoretical minimum number.

Because of its high efficiency and flexibility this approach has been selected in the two European Union research projects X-By-Wire and GUARDS on distributed fault-tolerand architectures. Timed messages will be supported in the next verion of the commercially available automotive electronics operating system ERCOS.

Bibtex

@article{ poledna:1997-21,
  author =       "Stefan Poledna and Peter Barrett and Alan Burns and Andy Wellings",
  title =        "Replica Determinism and Flexible Scheduling in Hard Real-Time Dependable Systems",
  journal =      "IEEE Transactions on Computers, Vol. 49, No. 2, pp. 100-111, February 2000",
  year =         "2000",
  month =        "Feb."
}

Download

Get rr-21-1997.pdf - Adobe PDF-format, (1501.64 KB; posted at November 06 2001)