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

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

Zhenpeng Xu (Jiangsu Automation Research Institute, Lianyungang, China), Zhenxing Yin (Jiangsu Automation Research Institute, Lianyungang, China) and Lili Wang (Jiangsu Automation Research Institute, Lianyungang, China)
DOI: 10.4018/ijapuc.2013070101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The fundamental goal of the log-based fault-tolerant scheme is to bring the system into a consistent global state without any orphan inconsistence. However, the existing Alvisi’s No-Orphans Consistency Condition is only sufficient on condition that the set of local checkpoints of failure processes keep consistent always. Independent of the specific log-based checkpointing and rollback-recovery fault tolerant scheme, an extended orphan-free consistency condition is derived based on PWD assumption in this paper. The definitions of the orphan inconsistence among the process state and the nondeterministic event during a rollback recovery were extended. Finally the essential requirement for message logs was specified to eliminate the possible orphan inconsistence among the process state during a rollback recovery. By contrast, the proposal is a practical and efficient constraint for the orphan-free recovery.
Article Preview

2. System Model

A distributed computing system is a finite set of computing processes, N={P1, P2, P3,…, Pn}, 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).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing