Search

Virtual machine (VM) snapshot, enabling a VM to be resumed from a previously recorded state, is an essential part of cloud infrastructures. Unfortunately, the snapshot data are likely to be lost due to the high rate of disk failures, so that the associated VM fails to recover properly. To enhance data availability without compromising application performance upon rollback recovery, it is desired to place multiple replicas of snapshot across disperse disks. However, due to the large size of replica, it induces non-trivial storage cost when managing massive snapshots in clouds. In this paper, we investigate this problem and find out that the semantic gap existed between snapshot creation and snapshot storing is one key factor inducing high storage cost. To this end, we propose SnapFiner, a page-aware snapshot system for creating and storing massive snapshot files efficiently. First, SnapFiner acquires a fine-grained page categorization with an in-depth page exploration from three orthogonal views, thereby discovering more pages that can be excluded from the snapshot. Second, SnapFiner varies the number of replicas for different page categories based on a page-aware replication policy, achieving low storage cost without compromising availability and performance. Third, SnapFiner handles the loss of pages either intentionally dropped upon snapshot creation or unexpectedly damaged due to disk failures, enabling proper system execution after rollback recovery. We have implemented SnapFiner on QEMU/KVM to justify its practicality for Linux guests. The experimental results demonstrate that SnapFiner reduces the storage cost by 33 and 69.5 percent respectively compared to our previous work PARS and the naive approach on QEMU/KVM and HDFS. [ABSTRACT FROM AUTHOR]

The rollback mechanism is critical in crash recovery and debugging, but its security problems have not been adequately addressed. This is justified by the fact that existing solutions always require modifications on target software or only work for specific scenarios. As a consequence, rollback is either neglected or restricted or prohibited in existing systems. In this paper, we systematically characterize security threats of rollback as abnormal states of non-deterministic variables and resumed program points caused by rollback. Based on this, we propose RollSec (for Rollback Security), which provides general measurements including state extracting, recording, and compensating, to maintain correctness of these abnormal states for eliminating rollback threats. RollSec can automatically extract these states based on language-independent information of software as protection targets, which will be monitored during run-time, and compensated to correct states on each rollback without requiring extra modifications or supports of specific architectures. At last, we implement a prototype of RollSec to verify its effectiveness, and conduct performance evaluations which demonstrate that only acceptable overhead is introduced. [ABSTRACT FROM AUTHOR]

A neoconservative coalition of oppositional forces, comprised of the Clinton wing of the Democratic Party and their allies in the Republican Party, the liberal mainstream media, and the deep state have promoted a new Cold War against Russia. This is intended as a mobilizing strategy to overturn the Trump presidency, weaken the Russian state, and reconstruct state legitimacy following years of decline in the quality of life and democracy in America. The coalition reconstructed the Cold War as an ideological tool in the interest of continuing to pursue domestic and global neoliberal policies and dealing with a fractious public disenchanted with government, its elected officials, the mainstream media, and a failing democracy. [ABSTRACT FROM AUTHOR]

This paper presents a new sender based message logging (SBML) protocol to tolerate simultaneous failures by using the beneficial features of FIFO group communication links effectively. The protocol can lift the inherent weakness of the original SBML by replicating the log information of each message sent to a process group into the volatile storages of its members. Therefore, even if only one process in a group survives at a time, our protocol can progress the execution of the entire system without stopping and restarting it. Also, it needs no extra control message by piggybacking the additional information on the control message for logging every previous protocol essentially requires. The experimental results show our protocol can be a low cost solution for addressing the important drawback of the original SBML based on group communication without RSN replication functionality. [ABSTRACT FROM AUTHOR]

Rollback is an effective technique to resume the system execution from a recorded intermediate state upon failures, without having to restart the entire system. However, in virtualized environments, rollback of a virtual machine cluster (VMC) produces high network traffic and long service disruption, particularly for a large cluster used for scientific computing, thereby imposing significant overhead both on network and applications. This paper proposes Piccolo, a fast and efficient rollback system, to restore a VMC from snapshot files over data center network. First, we exploit the similarity among VMC snapshots and leverage multicast to deliver the identical pages across VMs placed on disperse hosts, thereby bypassing unnecessary transmission of a large number of pages. Second, we analyze the impact on network traffic of varying VM placements in data center network, formulate the traffic aware placement as an optimization problem, and design a two-tier approximation algorithm that efficiently solves the problem. In addition to presenting Piccolo, we detail its implementation, and evaluate it by a set of experiments. The results show that Piccolo could achieve a significant reduction in terms of total sent data, network traffic and rollback latency compared to the existing generic techniques. [ABSTRACT FROM AUTHOR]

Cells exhibit stochastic behavior when the number of molecules is small. Hence a stochastic reaction-diffusion simulator capable of working at scale can provide a more accurate view of molecular dynamics within the cell. This article describes a parallel discrete event simulator, Neuron Time Warp-Multi Thread (NTW-MT), developed for the simulation of reaction diffusion models of neurons. To the best of our knowledge, this is the first parallel discrete event simulator oriented toward stochastic simulation of chemical reactions in a neuron. The simulator was developed as part of the NEURON project. NTW-MT is optimistic and thread based, which attempts to capitalize on multicore architectures used in high performance machines. It makes use of a multilevel queue for the pending event set and a single rollback message in place of individual antimessages to disperse contention and decrease the overhead of processing rollbacks. Global Virtual Time is computed asynchronously both within and among processes to get rid of the overhead for synchronizing threads. Memory usage is managed in order to avoid locking and unlocking when allocating and deallocating memory and to maximize cache locality. We verified our simulator on a calcium buffer model. We examined its performance on a calcium wave model, comparing it to the performance of a process based optimistic simulator and a threaded simulator which uses a single priority queue for each thread. Our multithreaded simulator is shown to achieve superior performance to these simulators. Finally, we demonstrated the scalability of our simulator on a larger Calcium-Induced Calcium Release (CICR) model and a more detailed CICR model. [ABSTRACT FROM AUTHOR]

It is not practically feasible to apply hardware-based fault-tolerant schemes, such as hardware replication, in mobile devices. Therefore, software-based fault-tolerance techniques, such as checkpoint and rollback schemes, are required. In checkpoint and rollback schemes, the optimal checkpoint interval should be applied to obtain the best performance. Most previous studies focused on minimizing the expected execution time or response time for completing a given task. Currently, most mobile applications run in real-time environments. Therefore, it is extremely essential for mobile devices to employ optimal checkpoint intervals as determined by the real-time constraints of tasks. In this study, we tackle the problem of determining the optimal inter-checkpoint interval of checkpoint and rollback schemes to maximize the deadline meet ratio in real-time systems and to build a probabilistic cost model. From this cost model, we can numerically find the optimal checkpoint interval using mathematical tools. The performance of the proposed solution is evaluated using analytical estimates. [ABSTRACT FROM AUTHOR]

In enacting a workflow process model, it is very important to control and trace each instance's execution as well as to keep it recoverable. Especially, the recoverability issue implies that the underlying workflow management system is able to not only provide the automatic error-detection functionality on its running exceptions but also to equip various autonomous recovery mechanisms to deal with the detected exceptional and risky situations. As a theoretical approach to resolve the autonomous workflow recovery issue, this paper tries to formalize a rollback-point decision tree structure based upon gateway-activities of a corresponding workflow process model, which is named as a gateway-centered workflow rollback decision model. We strongly believe that the proposed model ought to be one of those impeccable trials and pioneering contributions to improve and advance the capability of recovery in enacting workflow process models. [ABSTRACT FROM AUTHOR]

On the basis of bathymetric and seismic data, obtained during cruises 37 (2005) and 41 (2006) of R/V Akademik M.A. Lavrentiev, a new structural scheme of transverse faults in the forearc of the Central Kuril Islands was compiled, the fault kinematics was studied, and a model of the extension zone in the structural pattern of the study area was proposed. According to this model, the trench rollback and development of back-arc basins resulted from the continuous supply of material into the upper mantle convection cell owing to subduction and an increase in the dynamic pressure that pushes the subducting plate, causing it to migrate toward the ocean. [ABSTRACT FROM AUTHOR]

The current concerns with laggard growth and income inequality have led to a widespread set of demands for more regulation and higher taxation to reverse the trend. These two approaches move matters exactly in the wrong direction. The correct response is to find ways to reduce tax burdens and barriers to entry, and to reduce the political uncertainty associated with new government measures. It may well be too late, worldwide, for a substantial rollback in the welfare state. But the current proposals will only prolong the dismal results on both fronts in any arena in which they are tried. [ABSTRACT FROM AUTHOR]

Mobile ad hoc networks (MANETs) have significantly enhanced the wireless networks by eliminating the need for any fixed infrastructure. Hence, these are increasingly being used for expanding the computing capacity of existing networks or for implementation of autonomous mobile computing Grids. However, the fragile nature of MANETs makes the constituent nodes susceptible to failures and the computing potential of these networks can be utilized only if they are fault tolerant. The technique of checkpointing based rollback recovery has been used effectively for fault tolerance in static and cellular mobile systems; yet, the implementation of existing protocols for MANETs is not straightforward. The paper presents a novel rollback recovery protocol for handling the failures of mobile nodes in a MANET using checkpointing and sender based message logging. The proposed protocol utilizes the routing protocol existing in the network for implementing a low overhead recovery mechanism. The presented recovery procedure at a node is completely domino-free and asynchronous. The protocol is resilient to the dynamic characteristics of the MANET; allowing a distributed application to be executed independently without access to any wired Grid or cellular network access points. We also present an algorithm to record a consistent global snapshot of the MANET. [ABSTRACT FROM AUTHOR]

Mobile ad hoc networks (MANETs) are increasingly being employed for expanding the computing capabilities of existing cellular mobile systems and in the implementation of mobile computing grids. However, MANETs are susceptible to various transient as well as permanent failures and a fault tolerance technique is crucial in order to effectively utilize the constituent nodes as viable compute resources. Checkpointing and message logging based rollback recovery is a well established approach to provide fault tolerance in static and cellular mobile distributed systems; yet its use for achieving fault tolerance in MANETs is comparatively less explored. The existing recovery algorithms cannot be applied directly to MANETs due to their insufficiency in handling challenges like absence of static infrastructure, frequent node movement, constrained wireless bandwidth and limited stable storage. In this paper, we propose a checkpointing based rollback recovery protocol for clustered MANETs that determines the checkpointing frequency of a mobile node based on its mobility; thereby avoiding unnecessary checkpoints. The protocol uses a popular graph theoretic construct called connected dominating set to lower the communication overhead due to the recovery procedure. The findings of our scheme have been substantiated by the complexity analysis and simulation under varying network conditions. [ABSTRACT FROM AUTHOR]

The main focus in a single process checkpointing protocol is on finding optimal checkpoint interval to minimize the loss due to any fault, but in a distributed environment the main focus is on finding out and saving a global consistent state of the system. The challenge in finding a global consistent state is that interprocess communication creates dependencies that must be factored, otherwise the global checkpoint becomes useless. Mobile ad hoc networks throw up a plethora of challenges in tracking interprocess dependences including how to reliably save checkpoints in face of transience and node failures, where to save the checkpoints and how to reconstruct the stable global state from the nodes which are available after the fault. To add high availability and reliability to mobile networks, checkpoint based rollback recovery techniques are widely applicable. Checkpointing methods for traditional distributed systems cannot be applied directly to the mobile networks. This paper provides an overview of the available checkpointing strategies for mobile networks, comparing them on the various parameters. We conclude that no single strategy is optimal in all fault scenarios and that the perfect strategy may still be in the works. [ABSTRACT FROM AUTHOR]

Extreme-scale computing is set to provide the infrastructure for the advances and breakthroughs that will solve some of the hardest problems in science and engineering. However, resilience and energy concerns loom as two of the major challenges for machines at that scale. The number of components that will be assembled in the supercomputers plays a fundamental role in these challenges. First, a large number of parts will substantially increase the failure rate of the system compared to the failure frequency of current machines. Second, those components have to fit within the power envelope of the installation and keep the energy consumption within operational margins. Extreme-scale machines will have to incorporate fault tolerance mechanisms and honor the energy and power restrictions. Therefore, it is essential to understand how fault tolerance and energy consumption interplay. This paper presents a comparative evaluation and analysis of energy consumption of three different rollback-recovery protocols: checkpoint/restart, message logging and parallel recovery. Our experimental evaluation shows parallel recovery has the minimum execution time and energy consumption. Additionally, we present an analytical model that projects parallel recovery can reduce energy consumption more than 37% compared to checkpoint/restart at extreme scale. [ABSTRACT FROM AUTHOR]

Some systems work for a job with random working and processing times, and are checked at periodic and random times. When a failure occurs, we execute the backup operation to the latest checking time. First, the expected costs with periodic and random backups are formulated, and comparisons between periodic and random policies are made. Next, we focus on the backup policies when the system is checked at the iVth interval of working times, two total expected costs are obtained and optimal numbers N* which minimize them are derived analytically. Finally, one modified backup model in which failures are detected only at checking times is proposed and two expected costs are obtained. [ABSTRACT FROM AUTHOR]

Reverse computation is presented here as an important future direction in addressing the challenge of fault tolerant execution on very large cluster platforms for parallel computing. As the scale of parallel jobs increases, traditional checkpointing approaches suffer scalability problems ranging from computational slowdowns to high congestion at the persistent stores for checkpoints. Reverse computation can overcome such problems and is also better suited for parallel computing on newer architectures with smaller, cheaper or energy-efficient memories and file systems. Initial evidence for the feasibility of reverse computation in large systems is presented with detailed performance data from a particle (ideal gas) simulation scaling to 65,536 processor cores and 950 accelerators (GPUs). Reverse computation is observed to deliver very large gains relative to checkpointing schemes when nodes rely on their host processors/memory to tolerate faults at their accelerators. A comparison between reverse computation and checkpointing with measurements such as cache miss ratios, TLB misses and memory usage indicates that reverse computation is hard to ignore as a future alternative to be pursued in emerging architectures. [ABSTRACT FROM AUTHOR]

Abstract: The process of deploying a distributed system in a network of machines is often very complex, laborious and time-consuming, while it is hard to guarantee that the system will work as expected and that specific non-functional deployment requirements from the domain are supported. In this paper we describe the Disnix toolset, which provides system administrators or developers with automatic deployment of a distributed system in a network of machines from declarative specifications and offers properties such as complete dependencies, atomic upgrades and rollbacks to make this process efficient and reliable. Disnix has an extensible architecture, allowing the integration of custom modules to make the deployment more convenient and suitable for the domain in which the system is to be used. Disnix has been under development for almost four years and has been applied to several types of distributed systems, including an industrial case study. [Copyright &y& Elsevier]

Execution times of large-scale computational science and engineering parallel applications are usually longer than the mean-time-between-failures. For this reason, hardware failures must be tolerated by the applications to ensure that not all computation done is lost on machine failures. Checkpointing and rollback recovery is one of the most popular techniques to provide fault tolerance support to parallel applications. However, when a failure occurs, most checkpointing mechanisms require a complete restart of the parallel application from the last checkpoint. New advances in the prediction of hardware failures have led to the development of proactive process migration approaches, where tasks are migrated in a preventive way when node failures are anticipated, avoiding the restart of the whole application. The work presented in this paper extends an application-level checkpointing framework to proactively migrate message passing interface (MPI) processes when impending failures are notified, without having to restart the entire application. The main features of the proposed solution are: low overhead in failure-free executions, avoiding the checkpoint dumping associated to rolling back strategies; low overhead at migration time, by means of the design of a light and asynchronous protocol to achieve a consistent global state; transparency for the user, thanks to the use of a compiler tool and a runtime library and portability, as it is not locked into a particular architecture, operating system or MPI implementation. [ABSTRACT FROM AUTHOR]

Checkpointing and rollback recovery are widely used techniques for handling failures in distributed systems. When processes involved in a distributed computation are allowed to take checkpoints independently without any coordination with each other, some or all of the checkpoints taken may not be part of any consistent global checkpoint, and hence, are useless for recovery. Communication-induced checkpointing algorithms allow processes to take checkpoints independently and also ensure that each checkpoint taken is part of a consistent global checkpoint by forcing processes to take some additional checkpoints. It is well known that it is impossible to design an optimal communication-induced checkpointing algorithm (i.e. a checkpointing algorithm that takes minimum number of forced checkpoints). So, researchers have designed communication-induced checkpointing algorithms that reduce forced checkpoints using different heuristics. In this paper, we present a communication-induced checkpointing algorithm which takes less number of forced checkpoints when compared to some of the existing checkpointing algorithms in its class. [ABSTRACT FROM AUTHOR]

In recent years, High Performance Computing (HPC) systems have been shifting from expensive massively parallel architectures to clusters of commodity PCs to take advantage of cost and performance benefits. Fault tolerance in such systems is a growing concern for long-running applications. In this paper, we briefly review the failure rates of HPC systems and also survey the fault tolerance approaches for HPC systems and issues with these approaches. Rollback-recovery techniques which are most often used for long-running applications on HPC clusters are discussed because they are widely used for long-running applications on HPC systems. Specifically, the feature requirements of rollback-recovery are discussed and a taxonomy is developed for over twenty popular checkpoint/restart solutions. The intent of this paper is to aid researchers in the domain as well as to facilitate development of new checkpointing solutions. [ABSTRACT FROM AUTHOR]

Abstract: In system operations the term rollback is often used to imply that arbitrary changes can be reversed i.e. ‘rolled back’ from an erroneous state to a previously known acceptable state. We show that this assumption is flawed and discuss error-correction schemes based on absolute rather than relative change. Insight may be gained by relating change management to the theory of computation. To this end, we reformulate previously-defined ‘convergent change operators’ of Burgess into the language of groups and rings. We show that, in this form, the problem of rollback from a convergent operation becomes equivalent to that of ‘division by zero’ in computation. Hence, we discuss how recent work by Bergstra and Tucker on zero-totalized fields helps to clear up long-standing confusion about the options for ‘rollback’ in change management. [Copyright &y& Elsevier]

An alternative to classical fault-tolerant approaches for large-scale clusters is failure avoidance, by which the occurrence of a fault is predicted and a preventive measure is taken. We develop analytical performance models for two types of preventive measures: preventive checkpointing and preventive migration. We instantiate these models for platform scenarios representative of current and future technology trends. We find that preventive migration is the better approach in the short term by orders of magnitude. However, in the longer term, both approaches have comparable merit with a marginal advantage for preventive checkpointing. We also develop an analytical model of the performance for fault tolerance based on periodic checkpointing and compare this approach to both failure avoidance techniques. We find that this comparison is sensitive to the nature of the stochastic distribution of the time between failures, and that failure avoidance is likely inferior to fault tolerance in the long term. Regardless, our result show that each approach is likely to achieve poor utilization for large-scale platforms (e.g., 220 nodes) unless the mean time between failures is large. We show how bounding parallel job size improves utilization, but conclude that achieving good utilization in future large-scale platforms will require a combination of techniques. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we propose an enhanced Automatic Checkpointing and Partial Rollback (CaPR++) algorithm to realize Software Transactional Memory (STM), that employs partial rollback mechanism for conflict resolution. We have comparatively evaluated the "Abort" and "Partial Rollback" mechanisms for STMs. For purposes of comparison, we have used the state‐of‐the‐art RSTM system and for the "Partial Rollback", and we have used our earlier CaPR+ algorithm that has been enhanced for our requirements. Note that we have enriched the STAMP benchmarks with varied delayed transaction times. The results obtained demonstrate the effectiveness of the Partial Rollback mechanism over pure abort mechanisms for applications consisting of large transaction delays, with up to 1.6x performance gain for applications with large transactional delays. Our study makes the case for a hybrid system of pure aborts and partial rollbacks, which can extract the benefits of both mechanisms. Keeping in line with our study, we have proposed a hybrid implementation where some of the transactions of an application subscribe to abort mechanisms and the rest to partial rollback. Our initial implementation demonstrates various scenarios where the hybrid approach outperforms the pure abort and partial rollback approaches. [ABSTRACT FROM AUTHOR]

The use of a rollback buffer (RB) for hiding the rollback latency in log-based eager hardware transactional memory is proposed. The RB allows a transaction to abort without performing rollback, but still makes the transaction's old values immediately available. In effect, the rollback latency almost disappears. When running the Stanford transactional applications for multi-processing benchmark on a 16- core processor that implements the LogTM-SE, the speedup (decrease in execution time) achieved with a 2 KB RB is 15.8% on average. [ABSTRACT FROM AUTHOR]

Wormhole switching is a popular switching technique in interconnection networks. This technique is also prone to deadlocks. Adaptive routing algorithms provide alternative paths that can be used to escape congested areas and prevent some deadlocks to occur. If not designed carefully, these new paths may as well introduce deadlocks. A successful solution to deadlock prevention is to constrain the routing function such that it does not introduce any deadlock. Many necessary and sufficient conditions for deadlock-free routing have been proposed. The definition and the proof of these conditions are complex and error-prone. These conditions are often counterintuitive and difficult to understand. Moreover, they are not static, as they all require the analysis of configurations, i.e., the network state. The contribution of this paper is twofold. We present the first static necessary and sufficient condition for deadlock-free routing in wormhole networks. Our condition is much simpler and requires less assumptions than all previous ones. It is formally proven correct using an automated proof assistant. In particular, our condition applies to incoherent routing functions which was considered an open problem. Second, we prove the deadlock decision problem co-NP-complete for wormhole networks. [ABSTRACT FROM PUBLISHER]