Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Ω Line Problem in Optimistic Log-Based Rollback Recovery Protocol
IEICE TRANSACTIONS on Information and Systems Vol.E87-D No.7 pp.1834-1842
Publication Date: 2004/07/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Distributed, Grid and P2P Computing
optimistic log-based rollback recovery protocol,
piecewise deterministic assumption model,
Ω line problem,
Full Text: PDF
Optimistic log-based rollback recovery protocols have been regarded as an attractive fault-tolerant solution in distributed systems based on message-passing paradigm due to low overhead in failure-free time. These protocols are based on a Piecewise Deterministic (PWD) Assumption model. They, however, assumed that all logged non-deterministic events in a consistent global recovery line must be determinately replayed in recovery time. In this paper, we give the impossibility of deterministic replaying of logged non-deterministic event in a consistent global recovery line as a Ω Line Problem, because of asynchronous properties of distributed systems: no bound on the relative speeds of processes, no bound on message transmission delays and no global time source. In addition, we propose a new optimistic log-based rollback recovery protocol, which guarantees the deterministic replaying of all logged non-deterministic events belonged in a consistent global recovery line and solves a Ω Line Problem in recovery time.