From the early days of programming, the dependability of software has been a concern. The development of distributed systems that must respond in real-time and continue to function correctly in spite of hardware failure have increased the concern while making the task of ensuring dependability more complex. This dissertation presents a technique for improving confidence in software designed to execute on a distributed system of fail-stop processors. The methodology presented is based on a temporal logic augmented with time intervals and probability distributions. A temporal logic augmented with time intervals, Bounded Time Temporal Logic (BTTL), supports the specification and verification of real-time properties such as, "The program will poll the sensor every t to T time units." Analogously, a temporal logic augmented with probability distributions, Probabilistic Bounded Time Temporal Logic (PBTTL), supports reasoning about fault-tolerant properties such as, "The program will complete with probability less than or equal to p", and a combination of these properties such as, "The program will complete within t and T time units with probability less than or equal to p." The syntax and semantics of the two logics, BTTL and PBTTL, are carefully developed. This includes development of a program state model, state transition model, message passing system model and failure system model. An axiomatic program model is then presented and used for the development of a set of inference rules. The inference rules are designed to simplify use of the logic for reasoning about typical programming language constructs and commonly occurring programming scenarios. In addition to offering a systematic approach for verifying typical behaviors, the inference rules are intended to support the derivation of formulas expressing timing and probabilistic relationships between the execution times and probabilities of individual statements, groups of statements, message passing and failure recovery. Use of the methodology is demonstrated in examples of varying complexity, including five real-time examples and four combined real-time and fault-tolerant examples.

No description available.

Ph.D. / Electrical Engineering / The expected unreliability of nano-scale electronic components has renewed interest in the decades-old field of fault-tolerant logic design. Fault-tolerant design makes it possible to build reliable systems from unreliable components. This has spurred recent research into the application of classical FT techniques to nanoelectronics. Meanwhile, the growing gap between logic gate and wire delays, and the growing power consumption of clock generation and distribution circuits, in nanometer-scale silicon integrated circuits has renewed research in asynchronous, or clockless, logic design. This dissertation examines the application of triple modular redundancy (TMR), one of several FT circuit design techniques, to improve the reliability of a variety of clockless circuits and systems. A new fault model, appropriate for clockless circuits is derived and applied to measure the reliability of nonredundant and triplex micropipelines. A new circuit element that combines the functionality of a Muller C-element and a majority gate is introduced to solve special problems at the simplex-triplex interface. The effectiveness of asynchronous FT circuit design strategies based on the results of Monte Carlo simulation experiments with representative circuits modeled in Verilog hardware description language (HDL) is presented.

Graduation date: 1990

The operating clock frequency is determined by the longest signal propagation delay, setup/hold time, and timing margin. These are becoming less predictable with the increasing design complexity and process miniaturization. The difficult challenge is then to ensure that a device operating at its clock frequency is error-free with quantifiable assurance. Effort at device-level engineering will not suffice for these circuits exhibiting wide process variation and heightened sensitivities to operating condition stress. Logic-level redress of this issue is a necessity and we propose a design-level remedy for this timing-uncertainty problem. The aim of the design and analysis approaches presented in this dissertation is to provide framework, SABRE, wherein an increased operating clock frequency can be achieved. The approach is a combination of analytical modeling, experimental analy- sis, hardware /time-redundancy design, exception handling and recovery techniques. Our proposed design replicates only a necessary part of the original circuit to avoid high hardware overhead as in triple-modular-redundancy (TMR). The timing-critical combinational circuit is path-wise partitioned into two sections. The combinational circuits associated with long paths are laid out without any intrusion except for the fan-out connections from the first section of the circuit to a replicated second section of the combinational circuit. Thus only the second section of the circuit is replicated. The signals fanning out from the first section are latches, and thus are far shorter than the paths spanning the entire combinational circuit. The replicated circuit is timed at a subsequent clock cycle to ascertain relaxed timing paths. This insures that the likelihood of mistiming due to stress or process variation is eliminated. During the subsequent clock cycle, the outcome of the two logically identical, yet time-interleaved, circuit outputs are compared to detect faults. When a fault is detected, the retry sig- nal is triggered and the dynamic frequency-step-down takes place before a pipe flush, and retry is issued. The significant timing overhead associated with the retry is offset by the rarity of the timing violation events. Simulation results on ISCAS Benchmark circuits show that 10% of clock frequency gain is possible with 10 to 20 % of hardware overhead of replicated timing-critical circuit.

Thesis (M.S.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2004. / Dr. Feodor Vainstein, Committee Member; Dr. Doug Blough, Committee Chair; Dr. David Schimmel, Committee Member. Includes bibliographical references (leaves 71-75).

Thesis (M.S. in Electrical Engineering)--Washington State University. / Includes bibliographical references.

Thesis (Ph. D.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 114-120).

No description available.

No description available.