We propose a resource-efficient way to execute requests in Byzantine-fault-tolerant replication that is particularly well-suited for services in which request processing is resource-intensive. Previous efforts took a failure masking all-active approach of using all execution replicas to execute all requests; at least 2t + 1 execution replicas are needed to mask t Byzantine-faulty ones. We describe an asynchronous protocol that provides resource-efficient execution by combining failure masking with imperfect failure detection and checkpointing. Our protocol is parsimonious since it uses only t + 1 execution replicas, called the primary committee or PC, to execute the requests under normal conditions characterized by a stable network and no misbehavior by PC replicas; thus, a trustworthy reply can be obtained with the same latency, but with only about half of the overall resource use of the all-active approach. However, a request that exposes faults among the PC replicas causes the protocol to switch to a recovery mode, in which all 2t + 1 replicas execute the request and send their replies; then, after selecting a new PC, the protocol switches back to parsimonious execution. Such a request incurs a higher latency using our approach than the all-active approach, mainly because of fault detection latency. Practical observations point to the fact that failures and instability are the exception rather than the norm. That motivated our decision to optimize resource efficiency for the common case, even if it means paying a slightly higher performance cost during periods of instability

Research on software reliability has been active for several decades now and has produced massive amount of literature to explore new ideas, and system prototypes to experiment with the proposed ideas. Notwithstanding this proficiency, only in a few instances has research work found its way into industrial applications. This apparent uncoordination is exacerbated by the increasing need for quality and dependability guarantees in the more and more computerized modern world.

Distributed snapshots are an important building block for distributed systems, and, among other applications, are useful for constructing efficient checkpointing protocols. In addition to the imposed overhead of the existing distributed snapshot protocols, those protocols are not trivially applicable (if at all) in many of today's distributed systems, e.g., grid, mobile, and sensors systems. After presenting the shortages and the inapplicability of the most popular existing distributed snapshot protocols, this paper discusses improvement directions for the protocols. In addition, it presents a new and an important improvement for the most popular distributed snapshot protocol, which was presented by Chandy and Lamport in 1985. Although the proposed improvement is simple and easy to implement, it has significant benefits in reducing the software and hardware overheads of distributed snapshots. Then, the paper presents proofs for the safety and progress of the new protocol. Lastly, it presents a performance analysis of the protocol using stochastic models

Abstract Applications that are part of a mission‐critical information system need to maintain a usable level of key services through ongoing cyber‐attacks. In addition to the well‐publicized denial of service (DoS) attacks, these networked and distributed applications are increasingly threatened by sophisticated attacks that attempt to corrupt system components and violate service integrity. While various approaches have been explored to deal with DoS attacks, corruption‐inducing attacks remain largely unaddressed. We have developed a collection of mechanisms based on redundancy, Byzantine fault tolerance, and adaptive middleware that help distributed, object‐based applications tolerate corruption‐inducing attacks. In this paper, we present the ITUA architecture, which integrates these mechanisms in a framework for auto‐adaptive intrusion‐tolerant systems, and we describe our experience in using the technology to defend a critical application that is part of a larger avionics system as an example. We also motivate the adaptive responses that are key to intrusion tolerance, and explain the use of the ITUA architecture to support them in an architectural framework. Copyright © 2006 John Wiley & Sons, Ltd.

Distributed checkpointing is an important concept in providing fault tolerance in distributed systems. In today's applications, e.g., grid and massively parallel applications, the imposed overhead of taking a distributed checkpoint using the known approaches can often outweigh its benefits due to coordination and other overhead from the processes. This paper presents an innovative approach for distributed checkpointing. In this approach, the checkpoints are obtained using offline analysis based on the application level. During execution, no coordination is required. After presenting the approach, the authors proved its safety and present a performance analysis of it using stochastic models

Accomplishing the distributed snapshots problem in mobile systems is an important issue as well as in distributed systems. This work presents a distributed snapshots protocol for mobile computing systems. In addition, this protocol can be used for achieving an efficient checkpointing protocol in the mobile environment. Specifically, it is a robust adaptation of the classical distributed snapshots protocol, where the mobile hosts can still roam among the different cells within the mobile system. The main benefit of this work is to provide distributed snapshots for a mobile system without adding any restriction to the system, such as FIFO ordering among the application messages as required for a traditional distributed system.

An increasing number of computer systems are designed to be distributed across both local and wide-area networks, performing a multitude of critical information-sharing and computational tasks. Malicious attacks on such systems are a growing concern, where attackers typically seek to degrade quality of service by intrusions that exploit vulnerabilities in networks, operating systems, and application software. Accordingly, designers are seeking improved techniques for validating such systems with respect to specified survivability requirements. In this regard, we describe a model-based validation effort that was undertaken as part of a unified approach to validating a networked intrusion-tolerant information system. Model-based results were used to guide the system's design as well as to determine whether a given survivability requirement was satisfied.

This paper presents an objective measure, called overhead ratio, for evaluating distributed checkpointing protocols. This measure extends previous evaluation schemes by incorporating several additional parameters that are inherent in distributed environments. In particular, we take into account the rollback propagation of the protocol, which impacts the length of the recovery process, and therefore the expected program run-time in executions that involve failures and recoveries. The paper also analyzes several known protocols and compares their overhead ratio.

Abstract Checkpointingan application is the act of saving the application's state during its execution on stable storage, so that if the application fails it can berestartedfrom the last saved state, thereby avoiding loss of the work that was already done. Aheterogeneous checkpoint/restartmechanism allows one to restart an application on a possibly different hardware architecture and/or operating system than those in which the application was saved. This paper explores how to construct such a mechanism at the virtual machine level. That is, rather than dumping the entire state of the application process, the mechanism reported here dumps the state of the application as maintained by a virtual machine. During restart, the saved state is loaded into a new copy of the virtual machine, which continues running from there. The heterogeneous checkpoint/restart mechanism reported here was developed for the OCaml variant of ML. The paper reports on the main issues encountered in building such a mechanism and the design choices made, presents performance evaluations, and discusses some lessons and ideas for extending the work to native code OCaml and Java. Copyright © 2002 John Wiley & Sons, Ltd.

Proposes a new classification of executions with checkpoints that is based on the notion of k-rollback, indicating the maximal number of checkpoints that may need to be rolled back during recovery. The relation between known execution classes is explored, and it is shown that coordinated checkpointing, SZPF (strictly Z-path free) and ZPF (Z-path free) are 1-rollback mechanisms, while ZCF (Z-cycle free) is (n-1)-rollback, where n is the number of participants in an execution. A new class of executions, called d-BC (d-bounded cycles), is introduced, and is shown to be an [(n-1)/spl middot/d]-rollback mechanism (ZCF is a special case of d-BC for d=1). Finally, a d-BC protocol is presented. This protocol has the nice property that it does not impose any control information overhead on an application's messages, yet it only sends a few control messages of its own. Moreover, the protocol maintains information about recovery lines, which enables very efficient discovery of the most recent recovery line that existed a short time before the failure.

While a variety of checkpointing techniques and systems have been documented for long-running programs, they are typically not available for programmers that are non-systems experts. We detail a project that integrates three technologies, NetSolve, Starfish and IBP, for the seamless integration of fault-tolerance into long-running applications. We discuss the design and implementation of this project, and present performance results executing on both local and wide area networks.

This paper reports on the architecture and design of Starfish, an environment for executing dynamic (and static) MPI-2 programs on a cluster of workstations. Starfish is unique in being efficient, fault-tolerant, highly available, and dynamic as a system internally, and in supporting fault-tolerance and dynamicity for its application programs as well. Starfish achieves these goals by combining group communication technology with checkpoint/restart, and uses a novel architecture that is both flexible and portable and keeps group communication outside the critical data path, for maximum performance.

Article Free Access Share on Communication-processor tradeoffs in limited resources PRAM Authors: Adnan Agbaria Technion, Haifa Technion, HaifaView Profile , Yosi Ben-Asher Haifa University Haifa UniversityView Profile , Ilan Newman Haifa University Haifa UniversityView Profile Authors Info & Claims SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architecturesJune 1999 Pages 74–82https://doi.org/10.1145/305619.305628Published:01 June 1999Publication History 2citation240DownloadsMetricsTotal Citations2Total Downloads240Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF