26449771
Resolving error propagation in distributed systems
This paper investigates the problem of error propagation in distributed systems. To resolve this problem, a state preservation scheme is presented to save process states in main memory. Based on the state preservation, the processes suffering from error propagation can be recovered without involving stable storage. The recovery overhead is significantly reduced. In addition, a well-known single-source-all-destination graph algorithm is also utilized to find the optimal recovery points of the processes suffering from error propagation.
25953242
Restoration from Multiple Faults in WDM Networks without Wavelength Conversion
This paper addresses the problem of achieving full and fast restoration to tolerate as many faults as possible in wavelength-routed wavelength division multiplexing (WDM) networks with no wavelength conversion. We model the problem of finding the maximum number of faults tolerated as a constrained ring cover problem, which is a decomposition problem of exponential complexity. Three heuristic methods which guarantee that at least one fault can be tolerated are proposed. The Ear Decomposition (ED) method can always generate a decomposition to guarantee that only one fault can be tolerated. The Planar Decomposition (PD) method, which takes advantage of the bipartite graph model to generate a decomposition, can tolerate up to f faults, where f is the maximum cardinality between the two bipartite vertex sets. The Maximally Separated Rings (MSR) method uses the greedy method to find a decomposition to tolerate as many faults as possible. The marked-link (ML) method is also proposed to enhance the performance by marking some links, which are originally used for protection, available for normal transmissions. Finally, we also evaluate the number of faults tolerated and the blocking probabilities of these methods in three example networks.
6454250
An Efficient Time-Based Checkpointing Protocol for Mobile Computing Systems over Mobile IP
Time-based coordinated checkpointing protocols are well suited for mobile computing systems because no explicit coordination message is needed while the advantages of coordinated checkpointing are kept. However, without coordination, every process has to take a checkpoint during a checkpointing process. In this paper, an efficient time-based coordinated checkpointing protocol for mobile computing systems over Mobile IP is proposed. The protocol reduces the number of checkpoints per checkpointing process to nearly minimum, so that fewer checkpoints need to be transmitted through the costly wireless link. Our protocol also performs very well in the aspects of minimizing the number and size of messages transmitted in the wireless network. In addition, the protocol is nonblocking because inconsistencies can be avoided by the piggybacked information in every message. Therefore, the protocol brings very little overhead to a mobile host with limited resource. Additionally, by taking advantage of reliable timers in mobile support stations, the time-based checkpointing protocol can adapt to wide area networks.