Comparison of Recovery Schemes through a Mathematica Simulation

The Mathematica simulation described in this article compares two different schemes, the  iterative and the selective rollback methods, used in the recovery of computer networks from transient failures caused by environmental  factors or design errors.

by Silvia Heubach

In recent years, in part fueled by the growth of the Internet, networks of  computers such as ATM  systems,  LANs (local-area networks) and  WANs  (wide-area networks) have become more prevalent. All these systems consist of  parallel processes which communicate with each other, exchanging data or  combining results from the different processes. An area of concern is the  reliability and fault tolerance of these systems [Somai and Vaidya 1997]. The most difficult  types of failure to handle are transient failures caused by environmental  factors or design errors, as traces of their nature are long gone by the time  they are detected. To overcome this difficulty, a number of software  techniques have been suggested. The most common technique involves some form  of rollback and recovery method [Wu et al. 1990, Chandy et al. 1975, Kant 1978, Gray and Siewiorek 1991]. Typically, the state of the system  is saved at periodic intervals, a process called checkpointing. One of the popular error detection techniques is the use of acceptance  tests, for example a check for proper variable type  (e.g. a non-negative  value is expected, but a negative value is given as a function input).  Upon  detection of an error, the system needs to recover, that is to start over  from a checkpoint (= saved system state) that was established before the  failure occurred.  The main task for any recovery method consists of  identifying a  previously established checkpoint from which recovery is  possible.

The Mathematica simulation described in this article compares two different schemes, the  iterative and the selective rollback methods, for identifying the checkpoint  from which recovery is to be attempted. The first method proceeds one step at  a time, rolling back to the next most recent checkpoint and then attempting  recovery. The second method selects a checkpoint based on the distribution  function of the latency times (= time between a failure and its detection).  We simulate a set of  n parallel processes to collect "data" on the latency distribution and to  compare the cost of recovery for the two schemes. Furthermore, a  visualization of the processes will illustrate the sequence of  inter-connections, failures and acceptance tests.

Model Description

Before formalizing the model, we give an example. Below is a system with 4  processes (Subscript[P, 1]), (Subscript[P, 2]) , (Subscript[P, 3]), and (Subscript[P, 4]). Checkpoints (Subscript[CP, 4]), (Subscript[CP, 5]), and (Subscript[CP, 6]) indicate saved system states. Arrows between processes indicate  inter-connections. The small rectangle ("fail") indicates the occurrence of  a transient error  in process 3. Through the inter-connections, both process  2 (directly) and process 1 (indirectly via process 2) may have received  faulty data. Only process 4 is not affected. Once the acceptance test (AT) in  process 1 detects the error, all processes need to be rolled back to  checkpoint (Subscript[CP, 4]) to ensure recovery.

More formally, the system consists of n processes that carry out computations together with an additional process  which schedules (global) checkpointing and initiates recovery (this latter  process does not show up in the simulation).  In each of the n processes, inter-connections between the processes, failures and  acceptance tests occur at random times. 
To model this system, we assume  that the waiting times between events (inter-connections, failures, and  acceptance tests) are all independent exponential random variables. A failure  in process i is either detected by an acceptance test in the same process or by an  acceptance test in process k if there was a direct or indirect connection between process i and process k after the failure occurred. We will use the following parameters for the  exponential waiting times:
	(Subscript[λ, ij]) for inter-connections between process i and process  j
	(Subscript[φ, i]) for failures in process i
	(Subscript[α, i]) for acceptance tests in process i.
We assume that checkpointing occurs at fixed intervals of length C and that the time it takes to either save or reload a system state,  denoted by CL, is also constant. Checkpoints are numbered from 1 to tot+1, where tot = # of checkpointing intervals (= period between two checkpoints) covered  so far.  Due to limitations of storage space, only a certain number of checkpoints  can be maintained at any one time. Thus, once this number m is reached, the oldest checkpoint is overwritten by a new checkpoint.

Simulation

The user provides the following parameters: 
1) n, the number of processes (not counting the control process); 
2) icrange, the range (in hours) for average times between inter-connections;
3) failrange, the range (in hours) for average times between failures; and
4) acceptrange, the range (in hours) for average times between acceptance tests.

From the literature [ Shin and Lee 1984, Pamula 1990], the following intervals for average times (in 
hours) between events were taken:

	Inter-connections 	[ 0.25, 1]

	Failures		[ 10, 40 ]

	Acceptance Tests	[ 1, 2 ]

Thus, for an example with 4 processes, we enter:

n = 4;

icrange = {.25,1};

failrange = {10,40};

acceptrange = {1,2};

Since we are assuming exponential random variables, the parameter for  the distribution is the reciprocal of the expected value. Thus, to determine  the individual parameters, the range intervals are transformed by computing  the intervals for the reciprocals. Then a random number from these new  intervals is selected for each event. This is done using the function CreateRates. This function has as its  arguments the intervals for the average times.  The rates for each type of event are created as the lists icrates, failrates, and acceptrates.  The different event rates are combined into an n-by-(n+1) matrix. The inter-connection rate (Subscript[λ, ij]) between process i  and process j is listed as the (i,j) entry, the failure rate (Subscript[φ, i]) for process i is stored as the (i,i) entry and the acceptance rate (Subscript[α, i]) for process i is stored as the  (i, n+1) entry.

\(CreateRates[ic_List, fails_List, accept_List] := 
	
      Module[
			{icrates = 
            Table[Random[Real, {1/ic[\([2]\)], 1/ic[\([1]\)]}], {i, n}, {j, 
                n - 1}], 
			failrates\  = 
            Table[Random[Real, {1/fails[\([2]\)], 1/fails[\([1]\)]}], {i, 
                n}], \ acceptrates = 
            Table[Random[Real, {1/accept[\([2]\)], 1/accept[\([1]\)]}], {i, 
                n}], 
			rates\  = \ Table[0, {n}]}, 

		Do[
          rates[\([i]\)]\  = \ 
						Append[
              Insert[icrates[\([i]\)], failrates[\([i]\)], 
                i], 
											acceptrates[\([i]\)]], {i, 1, 
            n}]; 
		rates]\)

Here is an example of the parameters resulting from the function CreateRates:

			({{(Subscript[λ, ij]), 1, 2, 3, 4}, {1, *, 3.50163, 1.85276, 3.91859}, {2, 1.83752, *, 2.3015, 3.29872}, {3, 3.34154, 1.15867, *, 2.80303}, {4, 3.76839, 3.04845, 1.42542, *}})
			
			              ({{i, (Subscript[φ, i]), (Subscript[α, i])}, {1, 0.0803972, 0.0871607}, {2, 0.0979104, 0.0949468}, {3, 0.0801946, 0.970564}, {4, 0.0657209, 0.770418}})

Once all the rate parameters are computed, we need to determine the time 
until the next event. This time is the minimum of exponential times, hence 
also an exponential time with parameter

μ = (∑_(i = 1)^n)(∑_(j ≠ i)^n) (Subscript[λ, ij])+(∑_(i = 1)^n) (Subscript[φ, i])+(∑_(i = 1)^n) (Subscript[α, i])

Furthermore, the probability that the next event is the event with  parameter ρ∈{(Subscript[λ, ij]), (Subscript[φ, i]),(Subscript[α, i])} is given by ρ/μ. These probabilities are used as input for the  function WhichOne to determine which event takes place next. Imagine the interval [0,1]  partitioned by the event probabilities (they sum to 1). Each segment created  by the partition can be associated with a specific event. Now a uniform  random number from [0,1] is selected. This number falls into one of the  segments, indicating that the corresponding event takes place. The function  WhichOne makes use of the structure in which the rates, and hence the  corresponding probabilities, were ordered in the function CreateRates. The  variables to and from are used to keep track of which kind of connections have taken place. If   to  =  from,  a failure has occurred, and if to = n+1, then the event is an acceptance test.

WhichOne[probabilities_] :=

	Module[{event, eventcheck = 0,m = 0, problist},

		event = Random[];

		

		problist = Flatten[probabilities];

		While[eventcheck  < event,

			m = m+1;

			eventcheck = eventcheck + problist[[m]]

			];

		If[Mod[m,n+1]==0,

			to = n+1; from = Quotient[m,n+1],

			to = Mod[m,n+1];from = Quotient[m,n+1]+1;

			]

		]

To simulate the system of parallel processes and the detection of errors,  we need to keep track of when and where the failures occurred and which  processes have had inter-connections. This history will allow us to determine  which failures can be detected once an acceptance test occurs. Failures and  inter-connections are recorded, whereas acceptance tests either result in  detection of an error and corresponding reset, or have no consequence at all.   The n-by-n matrix descendants keeps track of inter-connections and the list  failures keeps tracks of whether or not a failure has occurred. Let's look at the  different events and what effects they have.

Failure occurred

If the failure is the very first one to occur in the system, then every element in the matrix descendants is set to 0 as none of the previous connections are of any relevance to  future failure detection. If the failure occurring is the first at a  particular process, then any previous connections of this process to other  processes are erased by setting the corresponding elements of the matrix descendants to zero. In both cases, the relevant entry in failures is set to 1 to record the error. If the simulation is used for data  collection, then the time at which the failure occurred is recorded in the  list failuretimes.

Acceptance Test (AT) occurred

If no failure has occurred in the process at which the AT takes place,  then all connections from this process to others are removed by setting the  corresponding entries in descendants to zero (no faulty data has been propagated). For any process in which a  failure is detected, all previous connections are erased and the entry in failures is set to zero. If the simulation is used for data collection, then the  latency time is recorded and  failuretime is reset to zero; if the simulation is used for cost comparison,  then  error recovery is initiated.

Inter-Connection occurred

The connection is recorded by setting the corresponding element in descendants to one. Any resulting indirect inter-connections are recorded in the same  manner.

Data Collection

We are now ready for the first part of the simulation, namely collecting  data for the latency distribution. A total of five simulations, each up to  time 200 (hours), are executed. In each of the simulations, the rate  parameters will be different, reflecting the changing nature of transient  errors. The latency times are written to the file simlagtimes. The time clock  is advanced by exponential times using the Mathematica package Statistics`ContinuousDistributions`. Note that the time clock  does not take into account the checkpointing period, as we assume that no  errors occur during those times. The code for the program is contained in the  notebook Simdata.nb.

To visualize the latency data, we can use the Mathematica packages Statistics`DataManipulation` and Graphics`Graphics`.

<< Statistics`DataManipulation`<< Graphics`Graphics`

lagtime  =  ReadList["simlagtimes"];

dx = 0.2;
\(	\ \ \ \(freq\  = \ 
        BinCounts[lagtime, {0, Max[lagtime], dx}];\)\)
      midpoints  =  
        Range[dx/2, Max[lagtime] + dx/2, dx];
\(\ \ \ \ \ \ BarChart[
		\ \ \ \ \ \ \ \ \ Transpose[{freq, 
          midpoints}], 
      PlotRange -> All, 
						PlotLabel\  -> 
        FontForm["Latency times", \ {"Times-Roman", 
            12}]]
\)

\(
\)

Visualization of the Simulation

We visualize the interplay of the processes using an n-by-n square grid together with a single column.  An inter-connection from  process i to process j is shown by coloring the square whose left lower corner is at position (i,j). Different colors are used for direct (cyan)  and indirect (magenta)  connections. A failure in process i is shown as black square on the diagonal of the grid in the (i,i) position. An acceptance test in process i is shown in row i of the additional column (counting upwards). The graphical display is  updated in parallel with the lists failure and descendants. Setting an element to zero in either of these two lists is reflected by  showing the corresponding square empty. Acceptance tests are erased in the  next step, as they do not have any relevance to future failure detection. 

 Three functions contribute to the visual display: grid, Conn, and DropConn. The function grid produces the basic grid for the start-up. The n-by-n grid shows connections and failures, whereas the n-by-1 column shows the  acceptance tests.

(*Joe Single-space next code and below, please. Thanks, David *)

grid[n_] := Module[{dim = n, i},

	Graphics[

	{Table[{Line[{{i,0},{i,dim}}],

			Line[{{0,i},{dim,i}}]},{i,0,dim}],

	 Table[Line[{{dim+i,0},{dim+i,dim}}],{i,1,2}],

	 Table[Line[{{dim+1,i},{dim+2,i}}],{i,0,dim}]},		

	 AspectRatio -> Automatic]]

The function Conn selects the color depending  on the event, as well as the text to be  displayed. It returns a colored square at the appropriate position, which is  then added to the current display.

Conn[x_, y_, c_] :=

   Module[{col,txt,i,j},

    col = Which[c == 0, RGBColor[0,1,0],  (*Acceptance*)

		 	    c == 1, RGBColor[0,.7,.8], (*direct connection*)

		 	    c == 2, RGBColor[.8,.2,.5], (*indirect connection*)

		 	    c == 3, RGBColor[0,0,0]];  (*failure*)

	j = Which[y == n+1,	x,

			  y != n+1, y];

	i = Which[y == n+1,	n+2,

			  y != n+1, x];		   	

	txt = Which[y == n+1, StringForm["`1`",from],

				x == y, StringForm[""],

				y != n+1, StringForm["`1`->`2`",i,j]];

					 	

	Graphics[{{col, Rectangle[{i-1,j-1},{i,j}]},

			  Line[{{i,j},{i-1,j},{i-1,j-1},{i,j-1},

			       {i,j}}],

			       {RGBColor[0,0,0],

			          Text[txt,{i-.5,j-.5}]}},

			  AspectRatio -> Automatic] ]

The function DropConn handles the resetting aspect once an acceptance test takes place. Rather  than just adding empty squares to the Graphics display to overwrite displays  of earlier events, this function selectively removes the appropriate colored  squares. The input to the function DropConn is the process number, the current list of Graphics elements for display,  and the variable case. If case == False, then only connections are removed. If case == True, then acceptance tests and failures will  also be removed. The  function DropConn computes the positions of the Graphics elements to be removed, and then  uses the built-in function Delete to complete the task.

\(\(DropConn[k_, connlist_List, case_] := 
	
        Module[{del\  = {}, i, m}, 
		\ \ If[
            case\  == \ False, 
						Do[
              AppendTo[del, 
                Position[connlist, Conn[k, i, m]]], 
								{i, 1, 
                n}, {m, 1, 2}], 
		\ \ \ \ \ \ \ \ 	Do[
              AppendTo[del, 
                Position[connlist, Conn[k, i, m]]], 
								{i, 1, 
                n + 1}, {m, 0, 
                3}]
		\ \ \ \ ]; 
\ \ \ \ \ \ \ \ \ del\  = \ 
            Flatten[del, 1]; 
				Delete[connlist, 
            del]
	];\)\)

The file Simviz.nb contains the code for the visualization. Whenever the  lists descendants and failure are updated, the corresponding visual elements are added or removed.  Failure times are not tracked and only a single simulation is executed. Here  are some examples of  output from the file Simviz.nb. Note that for each  event, the cumulative relevant history is displayed. Events are numbered  consecutively, and the current event is indicated in the title of the graph.  In all three cases, two consecutive events are displayed to show the  dynamics.

Indirect Connections

The first grid shows the relevant history up to Event 10,  an  inter-connection from process 1 to process 4.  Event 11 is an  inter-connection from process 4 to process 2, displayed as a cyan square in  row 2, column 4 with label 4->2.  Besides recording the actual event,  two additional squares have been  placed in row 2, indicating  the two resulting indirect connections  from  processes 1 and 3 to process 2 (displayed in magenta).

Failures

The two grids below show the cumulative history just before the first failure 
currently on record and the occurrence of that failure as Event 517. The 
occurrence of such a failure results in a complete clearing of all earlier 
connections. Note that other failures may have occurred earlier, but have 
been detected and thus are no longer taken into account.

Acceptance Test and Failure Detection

The two grids below show the detection of the failure in process 3 (Event 
517) through an indirect connection by an acceptance test in process 1. 
Notice that the grid for Event 527 does no longer show the acceptance test, 
and that all the connections from process 1 (cleared because of the 
acceptance test) and process 3 (detected error) to other processes have been 
cleared, thus erasing all squares in columns 1 and 3.

\(
\)

Comparison of Recovery Schemes

Recovery Schemes: Iterative versus Selective Method

Once an error has been detected, recovery is initiated. The system needs  to roll back at least to the checkpoint just prior to the failure to achieve  recovery (we assume that no other errors occur during the recovery phase).  The easiest way to achieve recovery is the iterative method. The system is rolled back to the most recent checkpoint and starts over  from there. If recovery from checkpoint k  (Subscript[CP, k]) is unsuccessful, i.e. the acceptance test still detects an error, a new  attempt is made from (Subscript[CP, k - 1]). This continues until recovery has been accomplished or the system has been  rolled back to the oldest checkpoint, (Subscript[CP, 1]). The iterative method has the advantage of rolling back exactly to the  checkpoint just prior to the failure, but it may take a long time to do so.  Parts of the code are evaluated several times over, making the process of  recovery lengthy. As time is money (we actually set cost = time), a faster  method is desirable.
The selective method is based on knowledge of the latency distribution. For example, if we  knew that the average latency time was 20 minutes, we might roll back  immediately to a checkpoint that has been established at least 20 minutes  ago. This method might overshoot the target checkpoint just prior to the  failure, but also avoids reevaluating parts of code several times, thus  saving time overall. At the core of the selective method is the comparison of  pairs of consecutive checkpoints for lower expected cost. The method starts  with the most recently established pair of checkpoints, and works backward  until it finds a checkpoint with (locally) lowest expected cost of recovery.
 To compute the expected cost of recovery, knowledge of the distribution of  the latency times is necessary. The theoretical derivation of this  distribution is made difficult by the dependencies introduced through the  inter-connections, even in the case of independent exponential random  variables. Thus, we will use the empirical distribution function of the  collected data instead. The empirical distribution function for a set of data  {(Subscript[x, 1]), (Subscript[x, 2]),...., (Subscript[x, n])} is defined as

			EDF(x) = ((# of data values  ≤  x)/n)
			
The function EDF will compute the empirical distribution function at x for a given list of data.

\(\(\(EDF[x_, 
        a_List]\)\(:=\)\(\ \)\(
\)\(		\)\(Module[{lag\  = \ Sort[a], 
          num\  = \ 0, \ 
          i\  = \ 1}, 
								While[\((\ 
            i\  <= \ Length[a]\  && \ 
              lag[\([i]\)] <= \ x\ )\), 
												num\  = \ 
            num\  + 1; 
												i\  = \ 
            i + 1]; 
							num/
          Length[a]
								]\)\(
\)\(				\)\)\)

We will now derive the cost of recovery for these two methods.

Cost of Recovery from Checkpoint k

A recovery attempt from a given checkpoint results in the same cost for  both methods; they differ in the way in which they select the checkpoint for  recovery. The cost of recovery is taken to be the time it takes to restart  the system and to re-evaluate the code until the acceptance test is passed.  Let 

	CL = time to save/load a checkpoint
	C   = time between checkpoints
	CT = cycle time = CL + C
	d    = time between last checkpoint and acceptance test

The cost for recovery from checkpoint k is given by 

	T(k)=(tot+1 - k) CT + CL + d
	
Let's now compare the two algorithms and see how they arrive at the  total cost.

Total Cost of Recovery for the Iterative Method

Assume that the error occurred between (Subscript[CP, k])  and (Subscript[CP, k - 1]). The iterative method first rolls back to (Subscript[CP, tot+1]), incurring cost T(tot+1). Then it rolls back to (Subscript[CP, tot]), incurring cost T(tot). This continues until the process has rolled back to (Subscript[CP, k]). The cumulative cost of recovery is thus given by

	        (∑_(i = k)^(tot + 1))T(i)  =  (∑_(i = 0)^rsteps)(i CT  +  CL + d ) = (rsteps + 1)(((rsteps CT)/2) +  CL  +  d )
	
where rsteps = tot + 1 - k = # of intervals covered by the rollback. The function itrecovery computes  the cost of iterative recovery based on the time of failure occurrence. The  variable tslcp indicates the time since the last checkpoint,  tcp1 denotes the time at which (Subscript[CP, 1]) was established, and cint denotes C, the time between checkpoints.

\(\(\(itrecovery[
        failuretime_]\)\(:=\)\(
\)\(	\)\(Module[{rsteps}, 
		If[
          failuretime >= \ tcp1, 
					rsteps\  = \ 
            Ceiling[\((time - tslcp - failuretime)\)/
                cint], 
			\ \ \ \ rsteps\  = \ 
            total]; 
		\((rsteps + 1)\) \((rsteps*cycle/2\  + \ CL\  + \ 
              tslcp)\)]\)\(
\)\(				\)\)\)

Total Cost of Recovery for the Selective Method

In the iterative method, the selection of the checkpoint from which  recovery is attempted is based on pairwise comparison of expected cost. If  the expected cost of recovery from (Subscript[CP, k]) is smaller than the expected cost of recovery from (Subscript[CP, k - 1]) , then recovery is attempted from (Subscript[CP, k]); otherwise, the expected cost of recovery from (Subscript[CP, k - 1]) and (Subscript[CP, k - 2]) are compared (until either recovery is attempted from the checkpoint with  lower cost or (Subscript[CP, 1]) is reached).
In order to compute the expected cost of recovery from a  given checkpoint, we need the probabilities that the failure occurred after (Subscript[CP, k]). This probability can be expressed in terms of the latency times (taking  into account that the exponential time clock for events does not take into  account saving of the system state):
	
      P(k):=P(failure occurred after (Subscript[CP, k])) = P(lagtime < (tot+1-k) C + d) = EDF((tot+1-k) C + d).

When computing the expected cost of recovery from a given checkpoint  k, we distinguish as to when the failure has happened. If the failure  occurred after (Subscript[CP, k]), then rolling back to (Subscript[CP, k]) will ensure recovery at cost T(k). However, if failure occurred between checkpoints m and m+1 (m<k), then rollback from (Subscript[CP, k]) will not result in recovery. It is assumed that the rollback proceeds  iteratively after this first attempt (for the cost computation). Therefore,  we have the following cases:

               ({{Failure occured , with probability, at cost}, {after   (Subscript[CP, k]), P (k), T (k)}, {between  (Subscript[CP, k - 1])   and (Subscript[CP, k]), P (k - 1) - P (k), T (k) + T (k - 1)}, {⋮, ⋮, ⋮}, {between (Subscript[CP, 1]) and (Subscript[CP, 2]), P (1) - P (2), T (k) + T (k - 1) +  ...  + T (1)}})
               
The expected cost of recovery from (Subscript[CP, k]) is thus:

	EC(k) = T(k)·P(k) + (P(k-1)-P(k))·(T(k)+T(k-1)) +  ⋯+(P(1)-P(2))·(T(k)+⋯+T(1))
	           = T(k)·P(1) + T(k-1)·(P(1)-P(k)) + ⋯+ T(1)·(P(1)-P(2))
	           =T(k)·P(1) + (∑_(r = 1)^(k - 1))T(r)·(P(1) - P(r + 1)) 
	         
This is the setup for the initial selection of the checkpoint for  recovery. Once rollback has been attempted, two possibilities can occur:  Recovery was successful (and we are done) or a new checkpoint must be  selected. In the latter case, we know that the error must have occurred  before the initially selected checkpoint. This changes the probabilities for  failure in the various checkpoint intervals, and the computation of the  expected cost of recovery from a given checkpoint is modified accordingly.  The second column in the above table is adjusted as follows (if recovery from  (Subscript[CP, m]) was unsuccessful):

	P(failure after CP k | failure before (Subscript[CP, m])) = ((P(k) - P(m))/(1 - P(m)))
	
	P(failure between (Subscript[CP, l]) and (Subscript[CP, l + 1])| failure before (Subscript[CP, m])) = ((P(l + 1) - P(l))/(1 - P(m)))
	
All terms have a common denominator 1-P(m);  it can be canceled out since it does not affect the comparison of the  expected cost of recovery from (Subscript[CP, k])  and  (Subscript[CP, k + 1]), respectively. The only adjustment necessary is for the factor multiplied by T(k). This results in the following revised formula for EC(k):
	
	EC(k) =T(k)·(P(1)-P) + (∑_(r = 1)^(k - 1))T(r)·(P(1) - P(r + 1)) 
	
where P = 0 initially, and P = P(m) if recovery from (Subscript[CP, m]) was unsuccessful.

The function selrecovery computes the total cost for selective recovery once an error is detected.  The variable total  denotes the number of checkpoint intervals currently established (which  may differ from the final number in the beginning stages). The quantities probs, cost (⟷T ), and ec are computed. Several attempts may be necessary; the variable overallsuccess is used to determine whether recovery has been successful or is  impossible. After each recovery attempt, the cost for the attempt is added to  the variable totcost. If another recovery attempt is necessary, then the variables P and ec are updated.

\(\(\(selrecovery[
        failuretime_]\)\(:=\)\(
\)\(	\)\(Module[{probs, cost, ec, ccp, 
          overallsuccess = False, itsuccess = False, \ P\  = \ 0, 
          totcost = 0}, 
		
		probs = 
          Table[EDF[tslcp + \((total + 1 - k)\) cint, lagtime], {k, 1, 
              total + 1}]; 
		cost = 
          Table[\((total + 1 - k)\) cycle + CL + tslcp, {k, 1, 
              total + 1}]; 
	\ \ ccp = 
          total + 1; \ \ \ \ \ \ \ \ \ \ \ \ \ \  (*\ 
          current\ CP\ *) 
	
		While[
          overallsuccess\  == \ False, 
			\ If[ccp\  == \ 1, \ 
            itsuccess\  = \ True]; 
			\ ec = 
            Table[cost[\([k]\)] \((probs[\([1]\)] - P)\) + 
                Sum[cost[\([l]\)] \((probs[\([1]\)] - 
                        probs[\([l + 1]\)])\), {l, 1, k - 1}], {k, 1, 
                ccp}]; 
			
			\ While[\((\ 
                itsuccess\  == \ False)\)\  && \((\ 
                ccp\  > 1)\), \ \ \ \ \ 
				\ \ \ \ \ \ \(If[
                ec[\([ccp]\)] >= ec[\([ccp - 1]\)], ccp\  = \ ccp - 1, 
                itsuccess\  = \ True];\)
				\ \ \ \ \ ];  (*\ 
            End\ While\ *) 
						totcost\  = \ 
            totcost + 
              cost[\([ccp]\)]; \ \ \ \ 
			\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  (*\ 
            Recovery\ attempt\ from\ CP\ ccp\ *) 
		\ \ \ \ \ \ \ \ timeccp\ \  = \ 
            time - \((tslcp + \((total + 1 - ccp)\) 
                    cint)\); 
			\ 
			\ \ \ \ \ \ If[
            failuretime\  >= \ 
              timeccp, \ 
				\ \ \ \ \ \ \ \ \ \ overallsuccess\  = \ 
              True, \ \ \  (*\ 
              recovery\ successful\ *) 
			\ \ \ \ \ \  (*\ 
              else\ *) \ \ \ \ \ \ \ \ \ \ \ 
					\ \ \ \ \ \ \ \ \ P = probs\ [\([ccp]\)]; 
				\ \ \ \ \ \ \ \ \ \ \ ccp\  = \ 
              ccp - 1; 
				\ \ \ \ \ \ \ \ \ \ \ itsuccess\  = \ 
              False; 
				\ \ \ \ \ \ \ \ \ If[
              ccp\  == \ 0, \ \ \ \  (*\ 
                no\ recovery\ possible\ *) 
					\ \ \ \ \ \ \ \ \ \ \ \ \ overallsuccess\  = \ True]
			\ \ \ \ \ \ \ \ \ \ \ \ ]\ \ \  (*\ 
            End\ If\ *) 
				\ \ \ \ \ \ \ 	
		]; \  (*End\ of\ While\ *) 
	totcost\ \ 
]\)\(\ \)\( (*\ 
        End\ of\ Module\ *) \)\)\)

\(
\)

Simulation for Cost Comparison

To compare the two recovery methods, 30 simulations (up to time 100 hours) were  executed  for each of the values for the checkpoint interval length C. The largest checkpoint interval length was chosen to be approximately the  median of the latency times. Furthermore, the total number of checkpoint  intervals to be maintained is computed from the latency distribution. The  ideal situation, namely storing every single checkpoint, may not be feasible  due to space constraints in the system. However, one would like to insure a  certain probability of successful recovery.  Using quantiles of the latency  distribution, the program computes the total length of time that needs to be  covered if either a 90% or 95% recovery rate is to be guaranteed and  determines the appropriate number of checkpoint intervals. For each  combination of interval length C and  recovery rate, the cost for both the iterative and selective  recovery method are written to a file for later analysis. The file names are  constructed during the simulation to reflect the parameter values.
The main  changes in the code (as compared to the file Simdata.nb) are in the part  relating to the occurrence of an acceptance test. A new variable detect keeps track of which failures are detected. If one or more failures are  detected, rollback for recovery is initiated. The critical time which determines whether recovery will be  successful is the time of the earliest failure occurrence  (in the case of multiple failures). The cost for the iterative and selective  method, TCI and TCS, respectively, are updated.   The modified code can be found in the file  Simcost.nb. This file also contains the code for displaying the data to  compare the two methods.

Results of Cost Comparison

The datafiles are read into Mathematica and displayed for each pair of parameters. Using the built-in packages  Graphics`MultipleListPlot` and Graphics`Graphics, graphs of the data for all  parameter combinations are displayed. As an example of the output, here are  the graphs for C = 0.1 and both recovery levels.

The difference between the two types of cost is quite pronounced; for most  simulations the selective method's cost is about 50% of the cost of the  iterative method.  This is to be expected as for small checkpoint intervals  there is a bigger chance that the failure did not occur in the most recent  checkpoint interval and therefore the selective method has to go through  several passes. To better see the effect of the checkpoint interval length on  the cost, the average cost for each parameter pair is graphed versus the  checkpoint interval length C.

As the checkpoint interval length approaches the median of the latency time 
distribution, the two methods have virtually identical cost. The reason for 
this effect is that for a checkpoint interval of this length, most of the 
time the failure will have occurred after the last checkpoint and therefore 
both the selective and the iterative method roll back to he most recent 
checkpoint.

Conclusion

The above simulations indicate that for a model with independent  exponential waiting times between events, the selective method is superior to  the iterative method. The savings are most pronounced when the checkpoint  interval is small. Further refinement of the model will take into account  storage cost for the saved system states to determine the optimal length for  the checkpoint interval C to minimize the overall cost.
To implement the selective method, the  latency distribution has to be determined. Since even a theoretically derived  distribution function would require data collection to estimate parameters  for the inter-event distributions, an approximate method can be implemented  instead. By first using the iterative rollback mechanism with very small  interval length C, the latency distribution can be estimated to within an error of C. A cost comparison between the selective method based on the approximate and the actual latency times, respectively, can be found in [Heubach and Pamula 1999].

References

Somai, A. K. and N. H. Vaidya, Understanding Fault Tolerance and Reliability, Computer, 1997.

Wu, K. L.  et al., Error Recovery in Shared Memory Multiprocessors Using Private Caches, IEEE Transactions on Parallel and Distributed Systems, April 1990.

Chandy, K. M. et al., Analytic Models for Rollback and Recovery Strategies in Database  Systems, IEEE Transactions on Software Engineering, March 1975.
K. Kant, A Model for Error Recovery with Global Checkpointing, Information Sciences, No 30, 1978.

Gray, J.  and D. Siewiorek, High Availability Computer Systems, Computer, Sep. 1991.

Shin, K. G.  and Y. H. Lee, Error Detection Process - Model, Design, and Impact on Computer  Performance,  IEEE Transaction on Computers, June 1984.

Pamula, R. S. . Global Checkpointing for a Concurrent Processing System, Int. Journal of Systems Sciences, 1990.

Heubach, S. and R. S. Pamula, Implementing an Approximate Probabilistic Algorithm for Error Recovery in Concurrent Processing Systems, AoM/IAoM 1999 Proceedings: Computer Science, Vol 17, pp. 50 - 55.

About the Author

Silvia Heubach is an assistant professor in the Department of Mathematics and Computer Science at California State University, Los Angeles. She holds a Ph.D. in Applied Mathematics from the University of Southern California, Los Angeles. Her areas of interest are probability, modeling and differential equations. 

Silvia Heubach
Department of Mathematics and Computer Science
California State University, Los Angeles
sheubac@calstatela.edu

Electronic Subscriptions

Included in the distribution for each electronic subscription are the files recovery.nb, Simviz.nb, Simdata.nb and simlagtimes.txt containing Mathematica code and data for the material described in this article.