Omega Line Problem in Optimistic Log-Based Rollback Recovery Protocol

Abstract

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 determinatedly replayed in recovery time. In this paper, we give the impossibility of deterministic replaying of logged non-deterministic event in a consistent golbal recovery line as a omega Line Program, because of asynchronous properties of distributed systems: no bound on the relative speeds of processes, no bound on message tranmission delays and no global time souce.