Ω Line Problem in Optimistic Log-Based Rollback Recovery Protocol

MaengSoon BAIK  SungJin CHOI  ChongSun HWANG  JoonMin GIL  ChanYeol PARK  HeonChang YOO 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E87-D  No.7  pp.1834-1842
Publication Date: 2004/07/01
Online ISSN: 
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
Keyword: 
distributed systems,  fault-tolerance,  optimistic log-based rollback recovery protocol,  piecewise deterministic assumption model,  Ω line problem, 

Full Text: PDF

Summary: 
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.