A Fault-Tolerant Scheduling Problem

Arthur L. Liestman, Roy H. Campbell

Research output: Contribution to journalArticlepeer-review


A real-time system must be reliable if a failure to meet its timing specifications might endanger human life, damage equipment, or waste expensive resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. Fault tolerance improves reliability by incorporating redundancy into the system design. A deadline mechanism has been proposed to provide fault tolerance in real-time software systems. The mechanism trades the accuracy of the results of a service for timing precision. Two independent algorithms are provided for each service subject to a deadline. The primary algorithm produces a good quality service, although its real-time reliability may not be assured. The alternate algorithm is reliable and produces an acceptable response. This paper introduces an algorithm to generate an optimal schedule for the deadline mechanism and discusses a simple and efficient implementation. The schedule ensures the timely completion of the alternate algorithm despite a failure to complete the primary algorithm within real time.

Original languageEnglish (US)
Pages (from-to)1089-1095
Number of pages7
JournalIEEE Transactions on Software Engineering
Issue number11
StatePublished - 1986


  • Real-time systems
  • scheduling
  • software fault tolerance
  • software reliability

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'A Fault-Tolerant Scheduling Problem'. Together they form a unique fingerprint.

Cite this