Fault-Tolerant Parallel and Distributed Systems

The most important use of computing in the future will be in the context of the global "digital convergence" where everything becomes digital and every­ thing is inter-networked. The application will be dominated by storage, search, retrieval, analysis, exchange and updating of information in a wide variety of forms. Heavy demands will be placed on systems by many simultaneous re­ quests. And, fundamentally, all this shall be delivered at much higher levels of dependability, integrity and security. Increasingly, large parallel computing systems and networks are providing unique challenges to industry and academia in dependable computing, espe­ cially because of the higher failure rates intrinsic to these systems. The chal­ lenge in the last part of this decade is to build a systems that is both inexpensive and highly available. A machine cluster built of commodity hardware parts, with each node run­ ning an OS instance and a set of applications extended to be fault resilient can satisfy the new stringent high-availability requirements. The focus of this book is to present recent techniques and methods for im­ plementing fault-tolerant parallel and distributed computing systems. Section I, Fault-Tolerant Protocols, considers basic techniques for achieving fault-tolerance in communication protocols for distributed systems, including synchronous and asynchronous group communication, static total causal order­ ing protocols, and fail-aware datagram service that supports communications by time. Front Matter....Pages i-xiii Front Matter....Pages 1-1 Comparing Synchronous and Asynchronous Group Communication....Pages 3-24 Using Static Total Causal Ordering Protocols to Achieve Ordered View Synchrony....Pages 25-54 A Fail-Aware Datagram Service....Pages 55-69 Front Matter....Pages 71-71 Portable Checkpointing for Heterogeneous Architectures....Pages 73-91 A Checkpointing-Recovery Scheme for Domino-Free Distributed Systems....Pages 93-107 Overview of a Fault-Tolerant System....Pages 109-121 An Efficient Recoverable DSM on a Network of Workstations: Design and Implementation....Pages 123-138 Fault-Tolerance Issues of Local Area Multiprocessor (LAMP) Storage Subsystem....Pages 139-153 Fault-Tolerance Issues in RDBMS on SCI-Based Local Area Multiprocessor (LAMP)....Pages 155-169 Front Matter....Pages 171-171 Distributed Safety-Critical Systems....Pages 173-194 Dependability and Other Challenges in the Collision Between Computing and Telecommunication....Pages 195-211 A Unified Approach for the Synthesis of Scalable and Testable Embedded Architectures....Pages 213-230 A Fault-Robust SPMD Architecture for 3D-TV Image Processing....Pages 231-245 Front Matter....Pages 247-247 A Parallel Algorithm for Embedding Complete Binary Trees in Faulty Hypercubes....Pages 249-265 Fault-Tolerant Broadcasting in a k -ary n -Cube....Pages 267-283 Fault Isolation and Diagnosis in Multiprocessor Systems with Point-to-Point Communication Links....Pages 285-300 An Efficient Hardware Fault-Tolerant Technique....Pages 301-314 Reliability Evaluation of a Task under a Hardware Fault-Tolerant Technique....Pages 315-327 Fault Tolerance Measures for m -ary n -Dimensional Hypercubes Based on Forbidden Faulty Sets....Pages 329-340 On-Line Fault Recovery for Wormhole-Routed Two-Dimensional Meshes....Pages 341-356 Front Matter....Pages 247-247 Fault-Tolerant Dynamic Task Scheduling Based on Dataflow Graphs....Pages 357-371 A Novel Replication Technique for Implementing Fault-Tolerant Parallel Software....Pages 373-384 User-Transparent Checkpointing and Restart for Parallel Computers....Pages 385-399 Back Matter....Pages 401-401 The most important uses of computing in the future will be those related to the global `digital convergence' where all computing becomes digital and internetworked. This convergence will be propelled by new and advanced applications in storage, searching, retrieval and exchanging of information in a myriad of forms. All of these will place heavy demands on large parallel and distributed computer systems because these systems have high intrinsic failure rates. The challenge to the computer scientist is to build a system that is inexpensive, accessible and dependable. The chapters in this book provide insight into many of these issues and others that will challenge researchers and applications developers. Included among these topics are: Fault-tolerance in communication protocols for distributed systems including synchronous and asynchronous group communication. Methods and approaches for achieving fault-tolerance in distributed systems such as those used in networks of workstations (NOW), dependable cluster systems, and scalable coherent interfaces (SCI)-based local area multiprocessors (LAMP). General models and features of distributed safety-critical systems built from commercial off-the-shelf components as well as service dependability in telecomputing systems. Dependable parallel systems for real-time processing of video signals. Embedding in faulty multiprocessor systems, broadcasting, system-level testing techniques, on-line detection and recovery from intermittent and permanent faults, and more. Fault-Tolerant Parallel and Distributed Systems is a coherent and uniform collection of chapters with contributions by several of the leading experts working on fault-resilient applications. The numerous techniques and methods included will be of special interest to researchers, developers, and graduate students.