Preface

xxiii

Contributors

xxxv

Acknowledgments

xxxix

PART I MODELS AND PARADIGMS

(272)

Formal Verification Techniques for Digital Systems

(24)

Masahiro Fujita

Satoshi Komatsu

Hiroshi Saito

Introduction

(1)

Basic Techniques for Formal Verification

(3)

About Formal Verification

(1)

BDD

(2)

Verification Techniques for Combinational Circuit Equivalence

(7)

Basic Approaches

(2)

Combinational Equivalence Checking by Using Internal Equivalence Points

(3)

False Negatives

(1)

Summary of Combinational Circuit Equivalence Techniques

(1)

Verification Techniques for Sequential Circuits

(10)

Introduction

(1)

FSM

(1)

An Implicit Method for Reachable State Representation

(4)

Equivalence Checking of Finite State Machines

(3)

Computation Tree Logic and Model Checking

(1)

Summary of Sequential Circuit Verification Techniques

(1)

Summary

(3)

References

(3)

Tolerating Arbitrary Failures With State Machine Replication

(30)

Assia Doudou

Benoit Garbinato

Rachid Guerraoui

Introduction

(4)

Motivation

(1)

Background

(1)

Contribution

(1)

Related Work

(1)

Roadmap

(1)

System Model

(1)

Execution and Communication Model

(1)

Byzantine Failure Model

(1)

Total Order Broadcast

(4)

Specification

(1)

Underlying Abstractions

(1)

Composing the Total Order Broadcast Algorithm

(2)

Weak Interactive Consistency

(8)

Overview

(1)

Underlying Abstractions

(3)

The WIConsistency Algorithm

(2)

About Certificates

(2)

Muteness Failure Detector

(8)

The Muteness Failure Model

(1)

Muteness Failure Detector Specification

(1)

Muteness Failure Detector Implementation

(3)

Interactions Between Ap and ID

(3)

Concluding Remarks

(5)

Modularity of Specifications

(1)

Modularity of Implementations

(1)

Impact on Performance

(1)

References

(2)

Model-Based Evaluation as a Support to the Design of Dependable Systems

(30)

Andrea Bondavalli

Silvano Chiaradonna

Felicita di Giandomenico

Introduction

(1)

The Role of Model-Based Evaluation in the Development of Dependable Systems

(3)

Dependability Modeling Methodologies and Tools

(7)

Combinatorial Modeling Techniques

(1)

Markovian Models

(3)

Non-Markovian Models

(2)

Tools Overview

(1)

Analytical Modeling to Support Design Decisions

(8)

The α-Count Mechanism

(1)

Figures of Merit and Assumptions

(2)

Model of α-Count

(3)

Evaluation of α-Count

(2)

Analytical Modeling to Support Fault Removal During Operational Life

(6)

The Maintenance Strategies

(1)

Figures of Merit and Assumptions

(1)

The Model

(3)

Numerical Evaluation

(2)

Summary

(5)

References

(5)

Voting: A Paradigm for Adjudication and Data Fusion in Dependable Systems

(28)

Behrooz Parhami

Introduction

(1)

Voting in Dependable Systems

(6)

Hardware Voting

(1)

Software Voting

(2)

A General Framework

(2)

Voting Schemes and Problems

(4)

A Taxonomy of Voting

(1)

Threshold Voting

(1)

Plurality Voting

(1)

Approval Voting

(1)

Voting for Data Fusion

(4)

Sensor Processing and Fusion

(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

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Dependable Computing Systems Paradigms, Performance Issues, and Applications

9780471674221

0471674222

Supplemental Materials

Summary

Author Biography

Table of Contents

Supplemental Materials

Rewards Program