rent-now

Rent More, Save More! Use code: ECRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

9780471674221

Dependable Computing Systems Paradigms, Performance Issues, and Applications

by ;
  • ISBN13:

    9780471674221

  • ISBN10:

    0471674222

  • Edition: 1st
  • Format: Hardcover
  • Copyright: 2005-10-05
  • Publisher: Wiley-Interscience
  • Purchase Benefits
  • Free Shipping Icon Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • eCampus.com Logo Get Rewarded for Ordering Your Textbooks! Enroll Now
  • Write a Review Icon Write a Review
List Price: $233.54 Save up to $0.17
  • Buy New
    $233.37
    Add to Cart Free Shipping Icon Free Shipping

    PRINT ON DEMAND: 2-4 WEEKS. THIS ITEM CANNOT BE CANCELLED OR RETURNED.

Summary

A team of recognized experts leads the way to dependable computing systems With computers and networks pervading every aspect of daily life, there is an ever-growing demand for dependability. In this unique resource, researchers and organizations will find the tools needed to identify and engage state-of-the-art approaches used for the specification, design, and assessment of dependable computer systems. The first part of the book addresses models and paradigms of dependable computing, and the second part deals with enabling technologies and applications. Tough issues in creating dependable computing systems are also tackled, including: * Verification techniques * Model-based evaluation * Adjudication and data fusion * Robust communications primitives * Fault tolerance * Middleware * Grid security * Dependability in IBM mainframes * Embedded software * Real-time systems Each chapter of this contributed work has been authored by a recognized expert. This is an excellent textbook for graduate and advanced undergraduate students in electrical engineering, computer engineering, and computer science, as well as a must-have reference that will help engineers, programmers, and technologists develop systems that are secure and reliable.

Author Biography

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.

Table of Contents

Preface xxiii
Contributors xxxv
Acknowledgments xxxix
PART I MODELS AND PARADIGMS
1(272)
Formal Verification Techniques for Digital Systems
3(24)
Masahiro Fujita
Satoshi Komatsu
Hiroshi Saito
Introduction
3(1)
Basic Techniques for Formal Verification
4(3)
About Formal Verification
4(1)
BDD
5(2)
Verification Techniques for Combinational Circuit Equivalence
7(7)
Basic Approaches
7(2)
Combinational Equivalence Checking by Using Internal Equivalence Points
9(3)
False Negatives
12(1)
Summary of Combinational Circuit Equivalence Techniques
13(1)
Verification Techniques for Sequential Circuits
14(10)
Introduction
14(1)
FSM
14(1)
An Implicit Method for Reachable State Representation
15(4)
Equivalence Checking of Finite State Machines
19(3)
Computation Tree Logic and Model Checking
22(1)
Summary of Sequential Circuit Verification Techniques
23(1)
Summary
24(3)
References
24(3)
Tolerating Arbitrary Failures With State Machine Replication
27(30)
Assia Doudou
Benoit Garbinato
Rachid Guerraoui
Introduction
27(4)
Motivation
27(1)
Background
28(1)
Contribution
29(1)
Related Work
30(1)
Roadmap
31(1)
System Model
31(1)
Execution and Communication Model
31(1)
Byzantine Failure Model
31(1)
Total Order Broadcast
32(4)
Specification
32(1)
Underlying Abstractions
33(1)
Composing the Total Order Broadcast Algorithm
34(2)
Weak Interactive Consistency
36(8)
Overview
36(1)
Underlying Abstractions
37(3)
The WIConsistency Algorithm
40(2)
About Certificates
42(2)
Muteness Failure Detector
44(8)
The Muteness Failure Model
44(1)
Muteness Failure Detector Specification
45(1)
Muteness Failure Detector Implementation
46(3)
Interactions Between Ap and ID
49(3)
Concluding Remarks
52(5)
Modularity of Specifications
52(1)
Modularity of Implementations
53(1)
Impact on Performance
54(1)
References
55(2)
Model-Based Evaluation as a Support to the Design of Dependable Systems
57(30)
Andrea Bondavalli
Silvano Chiaradonna
Felicita di Giandomenico
Introduction
57(1)
The Role of Model-Based Evaluation in the Development of Dependable Systems
58(3)
Dependability Modeling Methodologies and Tools
61(7)
Combinatorial Modeling Techniques
61(1)
Markovian Models
62(3)
Non-Markovian Models
65(2)
Tools Overview
67(1)
Analytical Modeling to Support Design Decisions
68(8)
The α-Count Mechanism
68(1)
Figures of Merit and Assumptions
69(2)
Model of α-Count
71(3)
Evaluation of α-Count
74(2)
Analytical Modeling to Support Fault Removal During Operational Life
76(6)
The Maintenance Strategies
76(1)
Figures of Merit and Assumptions
77(1)
The Model
77(3)
Numerical Evaluation
80(2)
Summary
82(5)
References
82(5)
Voting: A Paradigm for Adjudication and Data Fusion in Dependable Systems
87(28)
Behrooz Parhami
Introduction
87(1)
Voting in Dependable Systems
88(6)
Hardware Voting
89(1)
Software Voting
90(2)
A General Framework
92(2)
Voting Schemes and Problems
94(4)
A Taxonomy of Voting
94(1)
Threshold Voting
95(1)
Plurality Voting
96(1)
Approval Voting
97(1)
Voting for Data Fusion
98(4)
Sensor Processing and Fusion
99(1)
Components for Data Fusion
100(1)
Data Fusion Examples
101(1)
Dealing with Data Diversity
101(1)
Implementation Issues
102(5)
Impossibility Results for Voting
103(1)
Correctness Concerns
104(2)
Performance Considerations
106(1)
Unifying Concepts
107(3)
Toward a Common Terminology
107(2)
A Data-Centered Methodology
109(1)
Conclusion
110(5)
References
111(4)
Robust Communication Primitives for Wireless Sensor Networks
115(28)
Amol Bakshi
Viktor K. Prasanna
Introduction
115(2)
Defining Realistic Models
117(2)
Our System Model
119(2)
Permutation Routing in a Single-hop Topology: State-of-the-Art
121(4)
System Model
121(1)
Protocol for a Fault-Free Network
121(2)
Fault-Tolerant Permutation Routing
123(1)
Remarks
124(1)
An Energy-Efficient Protocol Using a Low-Power Control Channel
125(7)
Description
126(2)
Performance
128(3)
Extending the Basic Protocol: Handling Variance in Packet Transfer Latency
131(1)
Our Routing Protocol for a Faulty Network
132(3)
Handling Permanent Faults
132(1)
Handling Transient Faults
132(3)
Energy Balance
135(1)
Our Generalized Protocol for a Multichannel Network
135(5)
System Model
135(2)
Protocol for a Fault-Free Network With One Control Channel and Multiple Data Channels
137(3)
Concluding Remarks
140(3)
References
140(3)
System-Level Diagnosis and Implications in Current Context
143(28)
Arun K. Somani
Issues in Large and Complex Computing Systems
143(2)
System-Level Diagnosis
145(3)
Classification of Diagnosable Systems
148(9)
Uniquely Diagnosable Systems
150(2)
Partially Diagnosable Systems
152(1)
Excess-Diagnosable Systems
153(2)
Sequentially Diagnosable Systems
155(1)
Incrementally Diagnosable Systems
156(1)
Adaptively Diagnosable Systems
157(1)
Diagnosability Algorithms
157(3)
Diagnosability Problem in Uniquely Diagnosable Systems
158(1)
Diagnosability Problem Under Other Models
158(1)
Using Diagnosability Model: Example
159(1)
Diagnosis Algorithms
160(5)
Centralized Algorithms
160(2)
Adaptively Diagnosable Systems
162(1)
Distributed Algorithms
162(2)
Other Diagnosis Approaches
164(1)
Application of System-Level Diagnosis Algorithm
165(1)
Summary and Conclusions
166(5)
References
167(4)
Predicate Detection in Asynchronous Systems With Crash Failures
171(42)
Felix C. Gartner
Stefan Pleisch
Introduction
171(2)
Related Work
172(1)
Road Map
172(1)
Predicate Detection in Fault-Free Environments
173(4)
Distributed Computations
173(1)
The Predicate Detection Problem
174(1)
Properties of Predicates: Local and Stable
175(1)
Observation System
175(1)
The Problem of Observer Dependence
175(2)
Failures and Failure Detection
177(6)
Failure Model
177(1)
Types of Predicates and Their Truth Value
178(1)
Failure Detectors
179(1)
On Implementability of Failure Detectors
180(1)
Failure Detection in the Context of Predicate Detection
181(2)
Predicate Detection in Faulty Environments
183(11)
Predicates Capturing the Operational State of Processes
183(1)
The Extended Observation System
184(1)
The Impact of Failure Detection on Predicate Detection
184(1)
Predicates Properties
185(1)
Detection Modalities
186(5)
Detection Semantics
191(2)
Classification of Existing Work on Predicate Detection in Faulty Environments
193(1)
Solving Predicate Detection in Faulty Environments
194(15)
Impossibility of Perfect Predicate Detection using Failure Detectors
195(1)
Solvability Conditions for Perfect Predicate Detection
196(3)
Stabilizing Variants of Predicate Detection
199(3)
Detecting Local-State-Lattice-Based Modalities
202(1)
Detecting Cooperating-Monitor-Based Modalities
203(6)
Conclusion
209(4)
References
211(2)
Fault Tolerance Against Design Faults
213(30)
Lorenzo Strigini
Introduction
213(2)
Examples and Principles
215(10)
Fault-Tolerant Components
215(4)
Fault Tolerant Design: Redundancy and Failure Diversity
219(1)
The Role of Diversity
220(2)
Possible Dependability Goals
222(3)
Potential and Actual Benefits
225(5)
Potential Benefits
225(1)
Models and Empirical Evidence
226(2)
Other Potential Advantages and Concerns
228(1)
Adoption of Fault Tolerance Methods Against Design Faults
228(2)
Design Solutions
230(6)
The Role of Generic Fault Tolerance Techniques
231(1)
Algorithm- and Application-specific Techniques
231(1)
Component-structured Fault Tolerance
232(4)
Summary
236(7)
References
238(5)
Formal Methods for Safety Critical Systems
243(30)
Ali E. Abdallah
Jonathan P. Bowen
Nimal Nissanke
Introduction
243(2)
Cost of Failure
244(1)
What Formal Methods Offer
244(1)
Specification of Safety
245(2)
Historical Background
247(1)
Safety
248(5)
Dependability
248(2)
Formal Methods
250(2)
Cost Issues
252(1)
Application Areas
253(3)
Requirements
253(1)
Design
254(1)
Compilation
254(1)
Documentation
254(1)
Human-Computer Interface
255(1)
Complementary Methods
255(1)
Static Analysis
255(1)
Testing
256(1)
Standards
256(1)
Specification Framework
256(6)
Changes in States as Time Histories
256(3)
Representation of Equipment
259(1)
A Classification of Safety Requirements
259(1)
Specification of Safety Requirements
260(2)
System State and Behavior
262(3)
Train Tracks
262(1)
Railway Signals
263(1)
Railway Points
264(1)
Discussion
265(3)
Formal Methods Research
266(1)
Formal Methods Technology
266(1)
Education and Accreditation
267(1)
Standards
267(1)
Conclusion
268(5)
References
269(4)
PART II ENABLING TECHNOLOGIES AND APPLICATIONS
273(354)
Dependability Support in Wireless Sensor Networks
275(10)
Denis Gracanin
Mohamed Eltoweissy
Stephan Olariu
Ashraf Wadaa
Motivation and Background
276(3)
Service Centric Model
279(4)
Model Description
280(2)
Comparison With Other Models
282(1)
Conclusion
283(2)
References
283(2)
Availability Modeling in Practice
285(34)
Kishor S. Trivedi
Archana Sathaye
Srinivasan Ramani
Introduction
285(1)
Modeling Approaches
286(6)
Analytical Availability Modeling Approaches
287(1)
Non-state Space Models
287(2)
State Space Models
289(3)
Composite Availability and Performance Model
292(5)
Multiprocessor Sizing Based on Availability
292(2)
Multiprocessor Sizing Based on Performance
294(1)
Multiprocessor Sizing Based on Performance and Availability
294(3)
Digital Equipment Corporation Case Study
297(18)
Reliability Block Diagram (RBD) Model
299(1)
Fault Tree Model
300(1)
Availability Model for the VAXcluster Processing Subsystem
301(3)
Availability Model for the VAXcluster Storage Subsystem
304(5)
SPN Availability Model
309(2)
SPN Availability Model for Heterogeneous VAXclusters
311(4)
Conclusion
315(4)
References
315(4)
Experimental Dependability Evaluation
319(30)
Joao Gabriel Silva
Henrique Madeira
Field Measurement
321(2)
Field Data Collection
321(1)
Analysis of Field Data
322(1)
Fault Injection
323(14)
Components, Attributes, and Properties of a Fault Injection Experiment
324(3)
Fault Injection Technologies
327(5)
Fault Emulation Accuracy
332(5)
Robustness Testing
337(3)
Applying Robustness Testing
338(1)
Making Interfaces More Robust
339(1)
Recent Developments: Dependability Benchmarking
340(2)
Conclusion
342(7)
References
343(6)
A Dependable Architecture for Telemedicine in Support of Disaster Relief
349(20)
Stephan Olariu
Kurt Maly
Edwin C. Foudriat
Sameh M. Yamany
Thomas Luckenbach
Introduction
349(1)
Telemedicine---State of the Art
350(2)
The WIRM System Architecture
352(4)
WIRM Challenges
354(2)
A Novel 3D Data Compression Technique
356(2)
SPS Image Generation
356(2)
Interactive Remote Visualization
358(1)
An Overview of H3M---Our Wireless Architecture
359(7)
DMNA Protocol Operation
361(1)
Intra- and Intercluster Communication
362(1)
Bandwidth Reallocation and Sharing
363(1)
Specializing H3M to Disaster Relief
364(2)
Concluding Remarks
366(3)
References
366(3)
An Overview of IBM Mainframe Dependable Computing: From System/360 to Series
369(26)
Lisa Spainhower
Introduction
369(6)
Historical Overview
369(1)
Founding Concepts
370(2)
Guiding Principles
372(3)
Implementing Dependability
375(1)
Error Detection and Fault Isolation
375(5)
Failure Modes
375(1)
System/360: Objectives
376(1)
Fault Locating Tests
376(1)
TCM technology
377(1)
CMOS Technology
378(1)
Inline Error Checking
378(1)
CMOS Error Checking: Duplication
379(1)
Instruction Level Retry
380(6)
Concept Stage
380(1)
Initial Implementation
381(1)
ILR Challenges
382(3)
ILR in CMOS
385(1)
Handling Permanent CPU Failures
385(1)
Online Repair
386(5)
Special Purpose System/360 MPs
386(1)
System/370 Commercial MPs
386(1)
Service Processor Online Repair
387(1)
Power and Cooling Online Repair
388(1)
Channel Susbsystem Online Repair
388(1)
CPU Concurrent Repair
389(1)
Memory Fault Tolerance
389(2)
Summary
391(4)
References
392(3)
Tracking the Propagation of Data Errors in Software
395(24)
Martin Hiller
Arshad Jhumka
Neeraj Suri
Introduction
395(1)
Target System Model
396(1)
Overview of the Tool Suite
397(4)
Basic System Structure
397(2)
Work Process for Using Propane
399(2)
Setup: Experiment Design and Target Instrumentation
401(6)
Faults and Fault Triggers
401(1)
Error Types and Injection Locations
402(1)
Triggering the Error Injections
403(1)
Logging Variables, Memory Areas, Events
403(1)
Environment Simulators and Test Cases
404(1)
Target System Instrumentation
405(2)
Setup Using Description Files
407(1)
Injection: Running Experiments
407(1)
Analysis: Obtaining Error Propagation Characteristics
408(1)
Example Results Generated by Propane
409(5)
Propane's Attributes and Main Characteristics
414(1)
Summary
415(4)
References
416(3)
Integrated Reliable Real-Time Systems
419(30)
Mohamed Younis
Background
421(4)
Fundamental Terminology
421(2)
Fault Taxonomy
423(2)
Integration Issues
425(4)
Strong Partitioning (Fault Containment)
425(1)
Hybrid Redundancy Levels and Types
426(1)
Predicable Resource Sharing
426(1)
Interapplication Communication
427(1)
Use of COTS Hardware Environment
427(1)
Supporting Legacy Software
428(1)
Incremental Validation
428(1)
Few Forward Steps
429(3)
Strong Partitioning
429(1)
Architectural Support
430(1)
Scheduling Shared Resources
431(1)
Interapplication Synchronization
431(1)
An Example Aerospace Application
432(10)
Design Goals and Challenges
433(4)
Integration Approach
437(5)
Conclusion
442(7)
References
443(6)
Network Resilience by Emergent Behavior from Simple Autonomous Agents
449(30)
Bjarne E. Helvik
Otto Wittner
Introduction
449(1)
Network Resilience
450(7)
Design Parameters
450(2)
Span Versus End-to-End Reestablishment
452(1)
Protection
452(1)
Reconfiguration
453(1)
Self-Healing
454(1)
Comparison and Discussion
455(2)
Handling Routing and Resources in Networks by Emergence
457(3)
Finding a Short Path
457(2)
Finding Paths in Asymmetric Networks
459(1)
Cross-Entropy Based Path Finding
460(8)
The Cross-Entropy Method
461(1)
Mobile Agent Behavior
462(3)
Initialization and Selection Strategies
465(1)
Implementation
466(2)
Finding ``Best-Effort'' Primary/Backup Paths
468(5)
Policy Driven Design of Primary/Backup Path Patterns
468(2)
Path Cost and Detestation
470(2)
A Case Study
472(1)
Discussion
473(2)
Concluding Remarks
475(4)
References
475(4)
Safeguarding Critical Infrastructures
479(22)
David Gamez
Simin Nadjm-Tehrani
John Bigham
Claudio Balducelli
Kalle Burbeck
Tobias Chyssler
Introduction
479(1)
Attacks, Failures, and Accidents
480(3)
Telecommunications Vulnerabilities
481(1)
Electricity Vulnerabilities
482(1)
Solutions
483(3)
Agents
483(2)
Detection
485(1)
Response
486(1)
The Safeguard Architecture
486(11)
Generic Agents
488(1)
Telecommunication Agents
489(3)
Electricity Agents
492(5)
Future Work
497(1)
Conclusion
497(4)
References
498(3)
Impact of Traffic Self-Similarity on the Performance of Routing Algorithms in Multicomputer Systems
501(24)
Geyong Min
Mohamed Ould-Khaoua
Demetres D. Kouvatsos
Irfan U. Awan
Introduction
502(2)
The k-ary n-Cube and Dimension-Ordered Routing
504(2)
Modeling of Traffic Self-Similarity
506(1)
The Analytical Model
507(11)
Modelling the Traffic Generated by Source Nodes and on Network Channels
508(2)
Computing the Laplace-Stieltjes Transform of the Channel Service Time in Dimension i (S*i(s))
510(2)
Computing the Probability of Message Blocking in Dimension i (Pbi)
512(1)
Computing the Virtual Channel Occupancy Probabilities in Dimension i (Pv(i,τj))
513(2)
Calculation of the Mean Waiting Time at the Source Node (Ws)
515(1)
Calculation of the Mean Message Latency (LM)
515(1)
Validation of the Model
515(3)
Impact of Self-Similar Traffic on Routing Performance
518(1)
Conclusions
519(6)
References
520(3)
Appendix 19.1: Notation
523(2)
Some Observations on Adaptive Meta-Heuristics for Routing in Datagram Networks
525(38)
Albert Y. Zomaya
Tysun Chan
Miro Kraetzl
Introduction
525(1)
The Routing Problem
526(6)
Least-Cost Algorithms
527(1)
Design Characteristics of Routing Algorithms
528(2)
Current Methods in Datagram Routing
530(2)
Genetic Algorithms and Routing
532(4)
Unicast Routing
533(1)
Multicast Routing
533(1)
Fault Tolerance
534(1)
Capacity Assignment
534(1)
Some Remarks
535(1)
Genetic Routing Protocol Design
536(11)
Chromosome Encodings and Evaluation
536(1)
Path Genetic Operators
537(2)
Algorithm Overview
539(2)
Comparison of the GMP to OSPF and RIP
541(1)
Integrating the GMP with OSPF Under TCP/IP
542(2)
Execution Flow
544(1)
Fault Tolerance
545(2)
Genetic Routing Protocol Implementation
547(5)
Topologies
548(1)
Links
548(1)
Nodes
549(2)
Traffic
551(1)
Genetic Parameters
551(1)
Results and Analysis
552(8)
Variable Delay
553(1)
Variable Mutation
553(2)
Variable Crossover
555(2)
Delay Comparisons With RIP and OSPF
557(1)
Overhead Comparisons with RIP and OSPF
557(2)
Fault Tolerance
559(1)
Conclusions
560(3)
References
561(2)
Reconfigurable Computing for Cryptography
563(34)
Hassan B. Diab
Introduction
564(1)
Reconfigurable Computing
565(11)
ASICs, GPPs, and RCs
565(1)
History of RC
566(1)
FPGAs and Their Present State
567(1)
RC Systems
568(5)
Applications of RC Systems
573(3)
AES Cryptography
576(3)
Case Study: The Twofish Cipher on a Dynamic RC System
579(10)
Mapping Twofish
583(2)
Key-Schedule Mapping
585(3)
Performance Analysis
588(1)
Future of RC
589(1)
Conclusion
590(7)
References
591(6)
Dependability of Reconfigurable Computing
597(30)
Mohamed Younis
I-Hong Yeh
Nicholas Kyriakopoulos
Nikitas Alexandridis
Tarek El-Ghazawi
FPGA Preliminaries
598(5)
Programming Technology
598(2)
Logic Block Architecture
600(1)
Routing Architecture
601(2)
CAD for FPGA
603(1)
FPGA Fault Taxonomy
603(5)
FPGA Faults
604(2)
FPGA Fault Taxonomy
606(1)
Mapping FPGA Faults to the Taxonomy
607(1)
Handling FPGA Failures
608(13)
Common Terminology
609(1)
Mechanisms for Detection
610(7)
Approaches for Fault Recovery
617(4)
Conclusion and Open Issues
621(6)
References
622(5)
Index 627

Supplemental Materials

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Rewards Program