Critical issues in the design of distributed, fault-tolerant, hard real-time systems
P. Thambidurai, Kishor Shridharbhai Trivedi · 1988
In this thesis we study four important problems associated with the design of Distributed, Fault-Tolerant, Hard Real-Time systems: Agreement, Clock Synchronization, Reliability Modelling, and Task Scheduling. Previous models of Agreement in distributed systems have made the unrealistic assumption that either all faults are arbitrary or all faults are not arbitrary. By introducing a unique and natural fault classification we have developed a 'Unified' model of Interactive Consistency. Our model takes advantage of the fact that both non-malicious faults and some malicious faults do not have to satisfy the $N > 3t$ requirement. We do not require that the system designer make unrealistic or extreme assumptions; both arbitrary and non-arbitrary faults are allowed. Most reliability models of ultra-reliable systems have not considered the interactive consistency requirement in a rigorous manner; distributed fault-tolerant systems have been modelled simply as redundant systems. We have obtained closed form expressions for the reliability and the Mean Time to Failure of distributed fault-tolerant systems. These reliability models are based on our 'Unified' fault model. These expressions explicitly include the contribution of the interactive consistency algorithm, and the types of faults. Our models allow the system designer to predict reliability far more accurately than previously possible. Clock synchronization is a fundamental requirement of fault-tolerant systems used for real-time control applications. Using the concepts of Interactive Convergence and Approximate Agreement we derive the maximum synchronization skew for the MAFT system. Then we develop a new fault model for clock faults, analagous to the 'Unified' model, and show that tighter synchronization and higher clock subsystem reliability are possible. Currently there are no methods which guarantee that a non-periodic task can complete within its deadline in a hard real-time system. We consider this problem in the context of a redundant system and introduce a novel technique which can allow a non-periodic task to execute within its deadline. This is accomplished by dynamically varying the redundancy of tasks. With the use of modelling we show that the impact on system reliability is minimal.