Orphan-Free Consistent Condition for Log-Based Checkpointing and Rollback Recovery Scheme

2. System Model

A distributed computing system is a finite set of computing processes, N={P₁, P₂, P₃,…, P_n}, running concurrently, communicating only by exchanging messages (Chen, Gu, George, & Cheng, 2005; Elnozahy, Alvisi, Wang, & Johnson, 2002; Alvisi & Marzullo, 1998; Park, Woo, & Yeom, 2002; Park, Woo, & Yeom, 2003; Gupta, Chauhan, & Kumar, 2008). Without a common clock, the processes cannot record their local states at precisely the same instant (Gupta, Chauhan, & Kumar, 2008; Cao & Singhal, 1998; Koo & Toueg, 1987; Agbaria & Sanders, 2004; Brzezinsk, Kobusinska, & Szychowiak, 2006).

Distributed computing is asynchronous (Elnozahy, Alvisi, Wang, & Johnson, 2002). That means there are no bound on the relative speeds of processes and no global time source. The computation of the process is assumed to follow Piece-Wise Deterministic (PWD) model (Elnozahy, Alvisi, Wang, & Johnson, 2002; Alvisi & Marzullo, 1998; Park, Woo, & Yeom, 2002; Park, Woo, & Yeom, 2003). In other words, the process execution is a sequence of state intervals, each started by a nondeterministic event (Li & Wang, 2005). These experienced events among the process follow the irreflexive partial order, which can be denoted by happened-before relation for representing potential causality (Elnozahy, Alvisi, Wang, & Johnson, 2002).