Dependable Computing Systems

HASSAN B. DIAB, PhD, is Professor of Electrical and Computer Engineering, Faculty of Engineering and Architecture, American University of Beirut (AUB). He is currently Dean of the School of Engineering at AUB and Acting President of Dhofar University, Sultanate of Oman. He is the Associate Editor of Simulation: Transactions of the Society for Modeling and Simulation International and a founding member of the Arab Computer Society. ALBERT Y. ZOMAYA, PhD, is the CISCO Systems Chair Professor of Internetworking, School of Information Technologies, The University of Sydney, and Deputy Director for Information Technology of the Sydney University Biological Informatics and Technology Centre. Dr. Zomaya has been the chair of the IEEE Technical Committee on Parallel Processing and has been awarded the IEEE Computer Society's Meritorious Service Award.

• Preface xxiiiContributors xxxvAcknowledgments xxxixPart I Models and Paradigms 11. Formal Verification Techniques for Digital Systems 3Masahiro Fujita, Satoshi Komatsu, and Hiroshi Saito1.1 Introduction 31.2 Basic Techniques for Formal Verification 41.3 Verification Techniques for Combinational Circuit Equivalence 71.4 Verification Techniques for Sequential Circuits 141.5 Summary 24References 242. Tolerating Arbitrary Failures With State Machine Replication 27Assia Doudou, Benoît Garbinato, and Rachid Guerraoui2.1 Introduction 272.2 System Model 312.3 Total Order Broadcast 322.4 Weak Interactive Consistency 362.5 Muteness Failure Detector 442.6 Concluding Remarks 52References 553. Model-Based Evaluation as a Support to the Design of Dependable Systems 57Andrea Bondavalli, Silvano Chiaradonna, and Felicita di Giandomenico3.1 Introduction 573.2 The Role of Model-Based Evaluation in the Development of Dependable Systems 583.3 Dependability Modeling Methodologies and Tools 613.4 Analytical Modeling to Support Design Decisions 683.5 Analytical Modeling to Support Fault Removal During Operational Life 763.6 Summary 82References 824. Voting: A Paradigm for Adjudication and Data Fusion in Dependable Systems 87Behrooz Parhami4.1 Introduction 874.2 Voting in Dependable Systems 884.3 Voting Schemes and Problems 944.4 Voting for Data Fusion 984.5 Implementation Issues 1024.6 Unifying Concepts 1074.7 Conclusion 110References 1115. Robust Communication Primitives for Wireless Sensor Networks 115Amol Bakshi and Viktor K. Prasanna5.1 Introduction 1155.2 Defining Realistic Models 1175.3 Our System Model 1195.4 Permutation Routing in a Single-hop Topology: State-of-the-Art 1215.5 An Energy-Efficient Protocol Using a Low-Power Control Channel 1255.6 Our Routing Protocol for a Faulty Network 1325.7 Our Generalized Protocol for a Multichannel Network 1355.8 Concluding Remarks 140References 1406. System-Level Diagnosis and Implications in Current Context 143Arun K. Somani6.1 Issues in Large and Complex Computing Systems 1436.2 System-Level Diagnosis 1456.3 Classification of Diagnosable Systems 1486.4 Diagnosability Algorithms 1576.5 Diagnosis Algorithms 1606.6 Application of System-Level Diagnosis Algorithm 1656.7 Summary and Conclusions 166References 1677. Predicate Detection in Asynchronous Systems With Crash Failures 171Felix C. Gärtner and Stefan Pleisch7.1 Introduction 1717.2 Predicate Detection in Fault-Free Environments 1737.3 Failures and Failure Detection 1777.4 Predicate Detection in Faulty Environments 1837.5 Solving Predicate Detection in Faulty Environments 1947.6 Conclusion 209References 2118. Fault Tolerance Against Design Faults 213Lorenzo Strigini8.1 Introduction 2138.2 Examples and Principles 2158.3 Potential and Actual Benefits 2258.4 Design Solutions 2308.5 Summary 236References 2389. Formal Methods for Safety Critical Systems 243Ali E. Abdallah, Jonathan P. Bowen, and Nimal Nissanke9.1 Introduction 2439.2 Specification of Safety 2459.3 Historical Background 2479.4 Safety 2489.5 Application Areas 2539.6 Specification Framework 2569.7 System State and Behavior 2629.8 Discussion 2659.9 Conclusion 268References 269Part II Enabling Technologies and Applications 27310. Dependability Support in Wireless Sensor Networks 275Denis Gracanin, Mohamed Eltoweissy, Stephan Olariu, and Ashraf Wadaa10.1 Motivation and Background 27610.2 Service Centric Model 27910.3 Conclusion 283References 28311. Availability Modeling in Practice 285Kishor S. Trivedi, Archana Sathaye, and Srinivasan Ramani11.1 Introduction 28511.2 Modeling Approaches 28611.3 Composite Availability and Performance Model 29211.4 Digital Equipment Corporation Case Study 29711.5 Conclusion 315References 31512. Experimental Dependability Evaluation 319João Gabriel Silva and Henrique Madeira12.1 Field Measurement 32112.2 Fault Injection 32312.3 Robustness Testing 33712.4 Recent Developments: Dependability Benchmarking 34012.5 Conclusion 342References 34313. A Dependable Architecture for Telemedicine in Support of Disaster Relief 349Stephan Olariu, Kurt Maly, Edwin C. Foudriat, Sameh M. Yamany, and Thomas Luckenbach13.1 Introduction 34913.2 Telemedicine—State of the Art 35013.3 The WIRM System Architecture 35213.4 A Novel 3D Data Compression Technique 35613.5 Interactive Remote Visualization 35813.6 An Overview of H3M—Our Wireless Architecture 35913.7 Concluding Remarks 366References 36614. An Overview of IBM Mainframe Dependable Computing: From System/360 to Series 369Lisa Spainhower14.1 Introduction 36914.2 Error Detection and Fault Isolation 37514.3 Instruction Level Retry 38014.4 Online Repair 38614.5 Summary 391References 39215. Tracking the Propagation of Data Errors in Software 395Martin Hiller, Arshad Jhumka, and Neeraj Suri15.1 Introduction 39515.2 Target System Model 39615.3 Overview of the Tool Suite 39715.4 Setup: Experiment Design and Target Instrumentation 40115.5 Injection: Running Experiments 40715.6 Analysis: Obtaining Error Propagation Characteristics 40815.7 Example Results Generated by Propane 40915.8 Propane’s Attributes and Main Characteristics 41415.9 Summary 415References 41616. Integrated Reliable Real-Time Systems 419Mohamed Younis16.1 Background 42116.2 Integration Issues 42516.3 Few Forward Steps 42916.4 An Example Aerospace Application 43216.5 Conclusion 442References 44317. Network Resilience by Emergent Behavior from Simple Autonomous Agents 449Bjarne E. Helvik and Otto Wittner17.1 Introduction 44917.2 Network Resilience 45017.3 Handling Routing and Resources in Networks by Emergence 45717.4 Cross-Entropy Based Path Finding 46017.5 Finding “Best-Effort” Primary/Backup Paths 46817.6 Discussion 47317.7 Concluding Remarks 475References 47518. Safeguarding Critical Infrastructures 479David Gamez, Simin Nadjm-Tehrani, John Bigham, Claudio Balducelli, Kalle Burbeck, and Tobias Chyssler18.1 Introduction 47918.2 Attacks, Failures, and Accidents 48018.3 Solutions 48318.4 The Safeguard Architecture 48618.5 Future Work 49718.6 Conclusion 497References 49819. Impact of Traffic Self-Similarity on the Performance of Routing Algorithms in Multicomputer Systems 501Geyong Min, Mohamed Ould-Khaoua, Demetres D. Kouvatsos, and Irfan U. Awan19.1 Introduction 50219.2 The k-ary n-Cube and Dimension-Ordered Routing 50419.3 Modeling of Traffic Self-Similarity 50619.4 The Analytical Model 50719.5 Impact of Self-Similar Traffic on Routing Performance 51819.6 Conclusions 519References 520Appendix 19.1: Notation 52320. Some Observations on Adaptive Meta-Heuristics for Routing in Datagram Networks 525Albert Y. Zomaya, Tysun Chan, and Miro Kraetzl20.1 Introduction 52520.2 The Routing Problem 52620.3 Genetic Algorithms and Routing 53220.4 Genetic Routing Protocol Design 53620.5 Genetic Routing Protocol Implementation 54720.6 Results and Analysis 55220.7 Conclusions 560References 56121. Reconfigurable Computing for Cryptography 563Hassan B. Diab21.1 Introduction 56421.2 Reconfigurable Computing 56521.3 AES Cryptography 57621.4 Case Study: The Twofish Cipher on a Dynamic RC System 57921.5 Future of RC 58921.6 Conclusion 590References 59122. Dependability of Reconfigurable Computing 597Mohamed Younis, I-Hong Yeh, Nicholas Kyriakopoulos, Nikitas Alexandridis, and Tarek El-Ghazawi22.1 FPGA Preliminaries 59822.2 FPGA Fault Taxonomy 60322.3 Handling FPGA Failures 60822.4 Conclusion and Open Issues 621References 622Index 627

" … a very interesting and useful book." (IEEE Communications Magazine, October 2006) "…a solid collection of research papers on the specification, design, and assessment of dependable computer systems." (CHOICE, March 2006)