THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT PROCESSES WITH RECOVERY BLOCKS KG. Shin Y-H. Lee CRL.rTR —83 FEBRUARY 1983 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 1This work was supported in part by NASA Grant No. NAG 1-296. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

ABSTRACT Although backward error recovery with recovery blocks(RB's) has received considerable attention from many researchers, no attempt has been made to structure Its implementation alternatives and then to evaluate/analyze their effectiveness. In this report we consider three different methods of implementing RB's. These are the asynchronous, synchronous, and the pseudo recovery point implementations. Asynchronous RB's are based on the concept of maximum autonomy in each of concurrent processes. Consequently, establishment of RB's in a process is made Independently of others and unbounded rollback becomes a serious problem. In order to completely avoid unbounded rollback, it is necessary to synchronize the establishment of recovery blocks in all cooperating processes. Process autonomy is sacrificed and processes are forced to wait for the commitment to establishIng a recovery line, leading to inefficiency in time utilization. As a compromise between asynchronous and synchronous RB's, we propose to insert pseudo recovery points so that unbounded rollback may be avoided while maintaining process autonomy. We have developed probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, I.e. exponential distributions for related random variables. With these models we have estimated (i) the Interval between two successive recovery lines for asynchronous RB's, (ii) mean loss In computation power for the synchronized method, and (iii) additional overhead and rollback distance in case PRP's are used. i

TABLE OF CONTENTS 1. INTRODUCTION...................................................................................................... 2 2. EVALUATION OF ASYNCHRONOUS RECOVERY BLOCKS....................................... 6 2.1. Modeling Assumptions............................................................................... 5 2.2. A Model for Asynchronous Recovery Blocks............................................. 7 2.3. The Analysis of Asynchronous Recovery Blocks...................................... 9 3. SYNCHRONIZED RECOVERY BLOCKS.................................................................. 12 4. IMPLANTATION OF PSEUDO RECOVERY POINTS.................................................. 14 6. CONCLUSION................................................................................................. 16 ACKNOWLEDGEMENT...................................................................... 18 REFERENCES............................................................................... 18 ii

7 ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT PROCESSES WITH RECOVERY BLOCKS1 Kang G. Shin and Yann-Hang Lee Computing Research Laboratory Department of Electrical and Computer Engineering The University of Michigan Ann Arbor, Michigan 48109 ABSTRACT Although backward error recovery with recovery blocks(RB's) has received considerable attention from many researchers, no attempt has been made to structure its Implementation alternatives and then to evaluate/analyze their effectiveness. In this report we consider three different methods of implementing RB's. These are the asynchronous, synchronous, and the pseudo recovery point implementations. Asynchronous RB's are based on the concept of maximum autonomy in each of concurrent processes. Consequently, establishment of RB's in a process is made Independently of others and unbounded rollback becomes a serious problem. In order to completely avoid unbounded rollback, it is necessary to synchronize the establishment of recovery blocks in all cooperating processes. Process autonomy Is sacrificed and processes are forced to wait for the commitment to establishing a recovery line, leading to inefficiency in time utilization. As a compromise between asynchronous and synchronous RB's, we propose to insert pseudo recovery points so that unbounded rollback may be avoided while maintaining process autonomy. We have developed probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, i.e. exponential distributions for related random variables. With these models we have estimated (i) the interval between two successive recovery lines for asynchronous RB's, (ii) mean loss in computation power for the synchronized method, and (iii) additional overhead and rollback distance in case PRP's are used. work reported hes suppor s ted In part by National Aeronautics and Space Administration Grant No. NAG 1-296. Any opinions, findings, and conclusions or recommendations In this publication are those of the authors and do not necessarily reflect the view of NASA.

Shin and Lee: Analysis of Recovery Blocks 1. INTRODUCTION Recent advances In VLSI and communication network technologies have made distributed processing feasible. While distributed processing can theoretically be exploited to provide computation speedup, cost-effectiveness and tolerance of component failure, several problems remain to be solved before its full potential can be realized in practice. In this report, we consider one such problem: that of implementing backward error recovery for concurrent processes with recovery blocks. The best known technique of backward error recovery, the recovery block (RB), was proposed by Horning [1 ] and Randell [2]. It is a sequential program structure that consists of an acceptance test, a recovery point(RP), an alternative algorithms for a given process. A process saves its state at its recovery point and then enters a recovery region. At the end of a recovery block, the acceptance test is executed to check correctness of the computation results. In case an error is detected during the normal execution or the computation results fail to pass the acceptance test, the process rolls back to an old state saved at the previous RP and executes one of the other alternatives. Unfortunately, however, for cooperating concurrent processes the rollback of a process may cause other processes to roll back(this phenomenon is called rollback propagation ) because of process interactions and imperfect checking of global correctness. Moreover, rollback may propagate to further RP's since recovery points of Individual processes may not provide a globally consistent state for all processes involved. This rollback propagation continues until it reaches a recovery line at which a globally consistent state does exist. In the worst case, an avalanche of rollback propagation (called the domino effect) can push the processes back to their beginnings, thus resulting in loss of the entire computation done prior to the error occurrence. 2

Shin and Lee: Analysis of Recovery Blocks A detailed description of the domino effect can be found in [3]. For convenience let us consider Figure 1 to visualize rollback propagation. Process P1 begins to roll back because of unsuccessful acceptance test AT. This rollback propagates to the other two processes P2 and P3. Eventually, the whole system has to restart from recovery line RL2 and the computation done between RL2 and AT4 has to be discarded. The interval between the restart point and the time point at which an error is detected or the acceptance test fails, called the rollback distance, can be used to represent the computation loss in rollback recovery. The domino effect is the major obstacle in implementing the recovery block scheme for concurrent processes. The designer Is able to predict neither the time of the occurrence of process interactions nor that of the appearance of recovery lines. Nonetheless, it is not desirable to randomly place recovery points and acceptance tests without considering process characteristics. Otherwise, it is possible to have a disaster such as unbounded rollback propagations, a large rollback distance, and a great number of largely useless recovery points occupying large amounts of memory space, etc. Furthermore, decision on rollback propagation and determination of recovery lines will become more complex though they can be made in a centralized [4,5] or decentralized manner [6,7,8]. Several refinements have been proposed to overcome the drawbacks in this recovery block scheme. One approach is to put concurrent processes Into a controlled scope, either to synchronize the occurrence of acceptance tests or to direct process Interactions. For the former, Randell [2] has suggested the conversation scheme which requests every cooperating concurrent process to leave its acceptance test at the same moment (called test line). He has also proposed a language structure In an abstract form for the conversation scheme. Other mechanizations of the conversation scheme on the basis of the same concept but with more flexibility have been devised by Kim [9]. Synchronized rollback recovery schemes for transactions using a two-phase commitment protocol or transaction ordering are also 3

Shin and Lee: Analysis of Recovery Blocks studied in [10,11,12]. Russell has proposed that information be retained for directed interactions from producers to consumers so that rollback propagation can be blocked [13,14]. Another approach is to save additional states based on the occurrence of interactions; for example, the branch recovery point [16] and the system defined checkpoint (SDCP) [16]. In this report we propose to employ pseudo recovery points2 (PRP's) to alleviate the rollback propagation problem by allowing a process to restart at a PRP In case the process is forced to roll back by others as a result of rollback propagation. Therefore, we can classify these refinements into two categories, synchronized recovery blocks and pseudo recovery points, providing a contrast with the third category called asynchronous recovery blocks. To implement the rollback recovery schemes, we have to consider various trade-offs between these three categories and the characteristics of concurrent processes. A satisfactory compromise should include an acceptable delay in process completion due to rollbacks, the preservation of autonomy for each process, and programmer transparency. Therefore, optimal solutions may be a combination of these three categories. A quantitative analysis is necessary to justify the solutions. For example, it is necessary to determine the mean amount of computation undone in case processes roll back, the optimal interval between two successive synchronizations, the mean size of memory space required to save states, etc. However, because the program behavior is unknown and execution proceeds stochastically, accurate modelling is difficult. In this report, employing standard assumptions in computer performance analysis, we have developed a model to quantitatively describe the characteristics of rollback recovery schemes as well as their effectiveness. In the following sec2 We call It a pseudo recovery polnt(PRP) since there Is no acceptance test before the saving of process state at a PRP. The states recorded at PRP's may have been contaminated and thus can not be used to recover a failed process. 4

Shin and Lee: Analysis of Recovery Blocks tlon, several assumptions are discussed and then a model for asynchronous recovery blocks is introduced. Using this model, we employ simulation to present the probability distribution of the interval between two successive recovery lines and the mean number of states recorded during that Interval. In Sections 3 and 4, the synchronization method and the implantation of pseudo recovery points are evaluated respectively. The report concludes with Section 6. 2. EVALUATION OF ASYNCHRONOUS RECOVERY BLOCKS Let us consider the history diagram in Figure 1 to illustrate the activities of cooperating concurrent processes Pi, i=1,2,...n. Process Pi establishes its jth recovery point RPf without synchronizing with other processes. Interprocess communications are represented by arrowed horizontal lines. Let set Acl1,...,n, I.e. a subset of concurrent processes. Then one may find a combination of RPj for all i cA, which forms a recovery line for set A, denoted as RL,A for the rth recovery line. For simplicity superscripts in representing recovery lines will be omitted in the sequel as long as that does not result In ambiguity. The interval between two successive recovery lines RL, and RLr+ in process Pi is a random variable and denoted by X4. Since a recovery line provides globally consistent states to all members of process set A, it is reasonable to assume that X: is stochastically identical for all icA. Thus, Xr is used to represent the interval between the rth and (r +)th recovery lines. 2.1. Modeling Assumptions We make the following assumptions in our subsequent analyses. 1. Autonomous Processes: Cooperative autonomy is regarded as the most important requirement in distributed processing. Each process should be executed according to its own program and environment, almost as if there were no 5

Shin and Lee: Analysis of Recovery Blocks processes to interfere with. Thus, a process is executing independently of others as long as there is no conflict with others in accessing shared resources. Since synchronization is not enforced in this category of recovery blocks (i.e. asynchronous recovery blocks), processes will transmit messages or establish their recovery points independently of other processes. 2. Perfect Acceptance Test. Acceptance tests should detect all errors within the local process during the execution of recovery blocks and thus ensure the correctness of local execution. It is in general difficult to guarantee the complete correctness, but at least the computation results that have passed the acceptance test should be "acceptable"[3]. The local acceptance test may or may not detect external errors or erroneous messages because the local process is not aware of the global system and other processes. 3. Probability Distribution of Interactions. Usually, process behavior is modeled as an ordered sequence which in turn is specified by the program and dependent on the execution condition. Even if the processing sequence is given, the Interval between two successive interactions is variable due to conditional branches. Locking and waiting at shared resources make it even more uncertain. Nontheless, for both tractability and simplicity we have adopted here constant reference rates in the multiprocessor and exponentially distributed intervals between two successive message transmissions in the computer network. The Interval for two successive interactions between Pi and Pj is thus assumed to be exponentially distributed with mean 1/ \h and \i =ji for all i,j =1,2,..., n and itj. 4. Consistent Communications: Let two messages m7a and mb be sent from Pi to Pi. Consistent communications should satisfy: (i) every message sent from Pi to Pj will be received eventually by P, and (ii) maand mb are received by 6

Shin and Lee: Analysis of Recovery Blocks Pj in the same order as that they are sent. Notice that in some packetswitched computer networks, messages are allowed to be received by the destination out of order. However, the order can be kept easily, for example, by time-stamping messages at the time of transmission. 6. Distribution of Recovery Points: Because of process independence and the uncertainty of execution conditions, the appearances of recovery points are random and difficult to model. To avoid complexity, establishment of recovery points In a process is assumed to be an independent Poisson process with parameter ^ for process Pi. 2.2. A Model for Asynchronous Recovery Blocks Since Individual recovery points by themselves may not be sufficient in rollback recovery due to the possibility of unbounded rollback propagations, we consider In this report only the formation of recovery lines for asynchronous recovery blocks instead of separate individual recovery points. The requirements of a recovery line for processes Pi, for i= 1,2,...n, can be stated as follows: 1. Each recovery line has to include one recovery point RP! for every process Pi. 2. Let the moment of establishment of the jth recovery point In process Pi be t[RPJ] and let tqV be the moment of the qth Interaction from Pi to Pi.. For every pair (RPj, RPj ) in a recovery line, there does not exist an integer k such that t'ctE[t [RPJ], t [RPE ]] if t[RPJ] < t[RPf:] (otherwise, tye[t [RP:], t [RPP]]). This implies that no communication from Pi to Pi (and vice versa) can be sandwiched between t [RPJ ] and t [RP' ]. The basic idea underlying the model is to trace the occurrence of both recovery points and Interactions. Based on the assumptions in Section 2.1, random 7

Shin and Lee: Analysis of Recovery Blocks variable Xr can be modeled by a continuous-time Markov process starting from a recovery line (Rlr) and ending at the next recovery line (RLr4.1). For a set of processes, DA=^t Pi ci A where A=1,2,.....n, two types of states are defined: (a). End states SR and Sr+,: transitions start from Sr where all processes have formed the rth recovery line, and end at Sr+1 upon establishment of the (r + ])th recovery line. (b). Intermediate states S = (x1, x2,...,), where xi = If the previous action of Pi was an interaction, and xz= 1 if it was establishment of a recovery point. Occurrences of interactions and recovery points in a process make the system go through these states. Note that both Sr and Sr+l are equivalent to state (1,1.....1). We can establish the following transition rules: R1. The system goes to state (x1.., -xi lx 1+1... n) from state (x,..,zxi.l,O,xi 1....an) with rate / upon establishment of a recovery point in Pi. R2. The system leaves state ( x 1,.,_xt-i.li, 1 i.., t,,lxj+i..Xn) and enters state (zx1..xzix —1,,xi+,.. xj — O i+l,. X.7l) with rate Xi If there is an Interaction between Pi and Pj. R3. The system arrives at state (x 1,...xi- O,x0i +I1.xn) from state (x,.,z-i_-l,,i+..,xn) with transition rate E \X where Bi=j I xj=O, ji and jcAt. R4. The system can transfer directly from state 5i to state Sr + n with transition rate Z Lk. k=l 8

Shin and Lee: Analysis of Recovery Blocks Under these transition rules a Markov model is developed for three processes P1, Pa and P3, and presented in Fig. 2. The single-arrow lines are unidirectional transitions. The double-arrow lines are bidirectional transitions in which left-hand side parameters represent leftward transition rates and right-hand side parameters rightward transition rates. The number of states for a set of n processes is 2l +1. When ^=ij =A and Xj =X for all i, j c A, the model can be simplified since all Intermediate states S=(zxx2,..x,) containing exactly u 1's in (z12,...,n) can be replaced by a single state u. A simplified model is obtained under the following transition rules and presented in Fig. 3. R1'. For u = O, l...,n- 1, the system will move to state Su + from state Su with transition rate (n-u)/, when a new recovery point is formed. R2'. For all u >. 2, the system is able to leave state Su for state qu-2 with rate (u l). R3'. For all u t 1, there is a transition from state Su to state u-1 with rate u (n -u)X. R4'. The system can transfer directly from the entry state Sr to the terminal state Sr+i with transition rate n/A. 2.3. The Analysis of Asynchronous Recovery Blocks With the model developed above, we can characterize the behavior of asynchronous recovery blocks in terms of the degree of interprocess communications and the distribution of recovery points. With the exponentially distributed interprocess communications and recovery points, Xr for all r becomes stochastically Identical. Let X denote a random variable representing the interval between two successive recovery lines, 4 the number of states saved in process Pi during 9

Shin and Lee: Analysis of Recovery Blocks Interval X. The probability distribution of X and the mean value of Lk are derived below. A. The distribution of X Let the state space +=M0,1,2,....mn where m=2n be the set of states of the foregoing continuous-time Markov process with the following convention for numbering states: (a). Sr —> state 0, n (b). an intermediate state (z,,x2. x..,) — > state (xji2i-1 +1), and i=1 (c). Sr,.+ — > state m. Then, the Chapman-Kolmogorov equation becomes d r(t) = r(t)H dt where H is the (mxm) transition matrix [h(u,v)] in which the (u,v) element is the transition rate from state u to state v, and rn(t) Is a vector whose kth element is the probability that the system is in state k at time t. The initial condition is ir(0)=[lO,0...,O0]. The interval between two successive recovery lines, X, is equal to the time needed for transition from state 0 to state m. Therefore, the density function of X, namely fz (t), is given by f(t) (t) B. The mean value of Li Since we are only concerned with the number of recovery points established by process Pt during interval X, a discrete Markov chain is used. To compute the mean value of Li, a new Markov chain, denoted by Yd, is constructed based on the previous model with the following two steps. 10

Shin and Lee: Analysis of Recovery Blocks (a). Convert the previous model to a discrete model: The new chain, Yd, has the same states as the previous Markov process. n n In Let G = E Xij + E AVk be the normalization factor. The transition =l j=l,ji k=l probability from state u to state v in Yd is equal to: for u, = 0,1,...,m, p(LV) = hu.) If u v, and p(u,u)= 1 — - p(2,v) v=l,vv u (b). Arrivals at a state S, = (x:,x2..., X,...,n) where xi=1 can be grouped grouped into two classes. One is formed as a result of the occurrences of RP's in Pi and the other is formed as a result of interprocess communications and establishments of RP's in processes other than Pi. Accordingly, the state Su=(zx,x2,.....Xi....n) with xi=1 can be split into two states Su' and Su,, representing the two classes, respectively. Both states have the same departure processes as that of S,. However, all arrivals at state Su due to the occurrence of recovery points in Pi enter state Su' whereas all other transitions are made to Su". Hence the number of RP's associated with state Su' is represented by that of arrivals at S'. Figure 4 shows the conversion and the split of state S2 = (1,0,0) of the Markov chain for the three concurrent processes in Figure 2. With the new discrete model, Yd, we can calculate the the mean number of visits to state Su', denoted as Ns, and the mean value of Li using the following relationship: E(L) = E E(Nsu) where IYd Is the state space of Yd. Suppose process Pi detects an error or fails the acceptance test at one of Its recovery points RP", where j=1,2,...,Li. The rollback of Pi may propagate to k processes In the process set, 0A = \PL I ltEA where A=11,2,..,n3. Let D1k be the 11

Shin and Lee: Analysis of Recovery Blocks rollback distance associated with the k processes and R-Pt for j =1,2,..,Li. Then, X represents the supremum of these random variables, i.e., Dr. In Figure 5, the mean values of X are plotted as a function of n. It shows that X increases drastically when there is an increase in the number of processes involved in the rollback recovery. The density function of X, f (t), is plotted in Figure 6. For all the three cases In Fig. 6, there is a sharp pulse near t-=0, which is due to direct transitions between Sr and Sr+ and a longer transition time needed once the system enters Intermediate states. n n n Let p (= Xij)/( / k) which represents the relative ratio between t=1 j=l,j i k=l the density of interprocess communications and recovery point establishments. With a fixed value of p and varying values of I.'s and X's for three processes, we have performed computer simulation and the results are tabulated in Table 1. The minima of X and L1 occur when the distribution of recovery points among these processes is uniformly balanced (i.e., / 1=L2=/a3)~ The distribution of interprocess communications does play an important role in determining the probability of rollback propagation but has little effect on X and Li once the set of processes involved in rollback recovery is determined. 3. SYNCHRONIZED RECOVERY BLOCKS The simplest way of avoiding unbounded rollback propagations is to synchronize the establishment of recovery points during process execution. In this method, Interactions are inhibited between any pair of processes during their establishment of recovery points. There are three conceivable strategies in deciding when a synchronization request is to be issued: (1) at a constant interval; (2) when the time elapsed since the previous recovery line exceeds a specified value; or (3) when the number of states saved after the previous recovery line is larger than a prespecifled number. The Implementation of the first strategy is simple since the synchronization request is issued without any knowledge of the state of execution. 12

Shin and Lee: Analysis of Recovery Blocks Nevertheless, this strategy may become very inefficient since it is possible to make synchronization requests immediately after the formation of recovery lines. For the second and third strategies, rollback distance and the number of saved states are prevented from becoming too large. However, in this case each process must be aware of the occurrence of a recovery line whenever it is established. Upon the receipt of a synchronization request, every process has to prepare for establishing a recovery line and also has to wait for the commitment (for establishing a recovery line) from other processes before it executes an acceptance test. Thus, all cooperating processes perform their acceptance tests at the same Instant upon receiving the commitments from all other processes. Let P -ready, for j=1,2,...,n, be the flags In process Pi to indicate commitments from P,. The steps for synchronization in each process Pi are described as follows: 1. execute "its own normal process" until "acceptance test"; 2. set Pi -ready:= ON and then broadcast Pi -ready; 3. while not (all Pj -ready = ON) do receive messages; if a message is Pj -ready then set Pij-ready:= ON else record the message 4. do "acceptance test" and record process states. Establishment of recovery lines upon synchronization requests is shown In Figure 7. Synchronization causes the computation power to be diminished because processes have to wait for the commitment (as in step 3). Let yi be the interval between the receiving of a synchronization request and the moment that process Pi reaches Its next acceptance test (in step 1). Then, according to the assumptions In Section 2.1, yi is an exponentially distributed random variable with parameter i. 73

Shin and Lee: Analysis of Recovery Blocks Let Z=maxjyl, Y2,.. yn. The total loss in computation power is CL = (Z-yi). i=l The mean loss becomes n 1 CL. = nf(1-Fx(t))dt - 1 where F (t) Is the distribution function of Z, and equals fH(1-e it). i=l 4. IMPLANTATION OF PSEUDO RECOVERY POINTS In the construction of a recovery block, usually, an acceptance test is a number of executable assessments provided by the programmer and then followed by a state saving. Note that process states can also be recorded upon any other requests if they are considered useful in the rollback recovery. A pseudo recovery point (PRP) is defined as a recovery point that is established without a preceding acceptance test and is proposed here as an alternative for avoiding the domino effect in a set of cooperating concurrent processes. With a monitor as the interprocess communication means, Kim [15] and Kant and Silberschatz [16] discussed methods for implanting recovery points in a central manner. Similarly, we consider a method for implanting PRP's in the set of cooperating concurrent processes in a decentralized manner. To make every recovery point RPJ in process Pi maximally useful for rollback error recovery, there should be corresponding recovery points in the other processes that have to roll back as a result of the rollback propagation from Pi. If such recovery points do not actually exist, a pseudo recovery point, PRPWi, has to be Inserted in process Pi, for a given RPJ in process Pi. Further, in order to avoid the need of tracing recovery points at that particular moment, a PRP is established in each of the other processes involved for HPL. An algorithm for implanting PRP's is given below. (1). When P{ establishes a recovery point RFP, it broadcasts a PRP 14

Shin and Lee: Analysis of Recovery Blocks Implantation request to other processes. (2). If P, receives the implantation request, it records its state as PRPJ' upon the completion of the current instruction without an acceptance test. Then Pi, broadcasts the commitment Ci. (3). Every process executes its own normal task after it establishes RPJ or PRP'. However, the messages sent to a process by Pi prior to C, have to be retained in the state saved. Assume that process Pi detects an error before establishing RPj,+1 and that this error is local to Pi. The recovery line (called a pseudo recovery line, PRL) formed by RPA and all PRPi's is able to recover these processes even if the error has already propagated to other processes. However, when the error detected in Pi Is due to error propagation from another process, PL (and therefore not local to Pi), the contents of PRPj may have already been contaminated if this error occurred prior to establishing PRPY. The restart from the pseudo recovery line formed by both RPiJ and all PRPji' s may just reproduce the same error. Therefore, rollback propagation may continue until every process involved has rolled back to a pseudo recovery line past at least one of its recovery points. Most of the processes Involved are assured to reach the pseudo recovery line by rolling back past only one recovery point. A few processes may have to roll back past more than one RP due to random Interprocesses interactions, and this can not be avoided unless a forced synchronization Is employed as discussed in Section 3. Consequently, the pseudo recovery line allows the processes to have the shortest rollback distance for backward error recovery without synchronization. Note that the pseudo recovery line is now guaranteed to contain correct states of all concerned processes. An algorithm of rollback recovery with these pseudo recovery points is given by: (1). If an error is found in process Pi, set p:= i where p is a rollback pointer. 15

Shin and Lee: Analysis of Recovery Blocks (2). Pp rolls back to its previous recovery point Rfjp. All processes Pi affected by the rollback of Pp roll back to their respective pseudo recovery points PRPi. (3). For every affected processes Pi', if the rollback has not passed its most recent recovery point, then set p:= i' and go back to step 2. In Figure 8, the establishment of PRP's in processes P1, P2, and P3 is illustrated. When P3 fails its acceptance test ATe, all processes have to restart from the pseudo recovery line formed by (RP1, PRP12, PRP13) if P1 and P2 are affected by the rollback of P3. In the above algorithm, we can find that every process needs to preserve a recovery point for restart in case it fails. Also (n-1) pseudo recovery points are needed for a process to form a pseudo recovery line with other processes where n Is the total number of concurrent processes. It is therefore required to save n states for every RP, i.e. one RP and (n-l) PRP's, and all old RP's and PRP's except those In the pseudo recovery lines! PRL I i = l...,n, and RPJ is the most recent RP In Pi can be purged when a new recovery point is established, thereby reducing storage requirements for saving RP's and PRP's. Note that rollback distance is bounded by the supremum of Y 1.Y2,.,yn where yi is the interval between two successive recovery points of process Pi. The additional time overhead for every recovery point is (n-l)t, where tr is the time needed to record the process state. These overheads should be assessed against the gain of process autonomy and avoidance of unbounded rollback propagations. 5. CONCLUSION We have quantitatively evaluated three different recovery blocks employed in backward error recovery for concurrent processing. The recovery block dealt with In this report is defined in software and comprises an acceptance test and a state 16

Shin and Lee: Analysis of Recovery Blocks saving. The environment of concurrent processing considered here is not restricted to any particular method of interprocess communications or system structure. We have estimated the overhead required to avoid the domino effect when recovery or pseudo recovery points are employed. For both the synchronization method and the Implantation of pseudo recovery points, the overheads are largely related to the construction of synchronization, RP's and PRP's. They would become an unacceptable burden when synchronizations and pseudo recovery points are constructed frequently but interprocess communications rarely occur. At the other extreme, i.e. asynchronous recovery blocks, it may result in a longer rollback distance due to unlimited rollback propagations (in place of synchronization and PRP Insertion overheads). In this report, we have considered the distribution of the interval between two successive recovery lines instead of the actual rollback distance. The rollback distance after an error is detected is related to the probability of error occurrence, error detection, and rollback propagation, etc. However, the interval X does represent an upper bound for the real rollback distance. To select a suitable strategy or a combination of these three methods, we have to first examine the properties of concurrent processes such as the amount of interprocess communications and the distribution of recovery points. Then, we weigh the trade-off between the loss of computation power during normal operation and the Increase In response time due to rollback recovery. For instance, the asynchronous method or a longer synchronization period is not acceptable for time-critical tasks In which a delay in system response beyond a certain value, the system deadline, leads to a catastrophic failure. The Implantation of pseudo recovery points is also Inefficient for concurrent processes when they establish recovery points frequently(thus requiring many PRP's to be implanted) and rarely communicate with each other. In general, if more knowledge of the execution state in concurrent 17

Shin and Lee: Analysis of Recovery Blocks processes can be obtained, a better strategy for implementing recovery blocks can be derived. ACKNOWLEDGEMENT The authors are grateful to Rick Butler and Milton Holt at NASA Langley Research Center for both financial and technical support and C. M. Krishna at The University of Michigan for technical discussions. REFERENCES [1]. J. Horning, H. C. Lauer, P. M. Melliar-Smith, and B. Randell, "A program structure for error detection and recovery," Lecture Notes in Computer Science, Vol. 16, Springer-Verlag, 1974, pp. 171-187. [2]. B. Randell, "System structure for software fault tolerance," IEEE Trans. on Software Eng., Vol. SE-1, No. 2, June 1975, pp. 220-232. [3]. B. Randell, P. A. Lee and P. C. Treleaven, "Reliability issues in computing system design," Computing Surveys, Vol. 10, No. 2, June 1978, pp. 123-165. [4]. Y. H. Lee and K. G. Shin, "Rollback propagation detection and performance evaluation of FTMR2M - a fault-tolerant multiprocessor," Proc. of Int'l Symp. on Computer Architecture, 1982, pp. 171-180. [6]. Y. H. Lee and K. G. Shin, "Design and evaluation of fault-tolerant multiprocessor using hardware recovery block," Technical Report, Comp. Res. Lab., Dept. of Electrical and Computer Eng., The Univ. of Michigan, CRL-TR-6-82, 1982. [6]. P. M. Merlin and B. Randell, "State restoration in distributed systems," Proc. of 8-th lnt' Conf. on Fault-Tolerant Computing, 1978, pp. 129-134. [7]. W. G. Wood, "A decentralized recovery control protocol," Proc. of 11-th Int'l Conf. on Fault-Tolerant Computing, 1981, pp. 159-164. [8]. K. Tsuruoka, A. Kaneko and Y. Nishihara, "Dynamic recovery schemes for distributed processes," Proc. of Reliab ility in Distributed Software and Database Systems, 1981, pp. 124-1 30. 18

Shin and Lee: Analysis of Recovery Blocks [9]. K. H. Kim, "Approaches to mechanizations of the conversation scheme based on monitors," IEEE Trans. on Software Eng., Vol. SE-8, No.3, May 1982, pp. 189-197. [10]. J. N. Gray, "Notes on database operating systems, " Operating Systems: A advanced course, edited by R. Bayer, et al., Springer-Verlag, 1979, pp.393481. [11]. W. H. Kohler, "A survey of techniques for synchronization and recovery in decentralized computer systems," Computing Surveys, Vol. 13, No. 2, June 1981, pp. 149-183. [12]. G. Ferran, "Distributed checkpointing in a distributed data management system," Proc. of Real Time Systems Symp., 1981, pp. 43-49. [13]. D. L. Russell, "Process backup in producer-consumer systems," Proc. of 6th ACM Symposium on Operatitng System Principles, Nov. 1977, pp. 151167. [14]. D. L. Russell, "State restoration in systems of communicating processes," IEEE Trans. on Softuware Eng., Vol. SE-6, No. 2, March 1980, pp. 183-194. [16]. K. H. Kim, "An approach to programmer-transparent coordination of recovering parallel processes and its efficient implementation rules," Proc. of Int'l Conf. on Parallel Processing, 1978, pp. 58-68. [16]. K. Kant and A. Silberschatz, "Error recovery in concurrent processes," Proc. of COMPSAC, 1980, pp. 608-61 4. 19

PI P2 Ps time! %P20 l RPR1 RP? —.r- -1 —/ —RP- \% RPlRPRP R^22~RP1 RL2 RP33 RP12 RP - RP3 AT' interaction Pl fails at AT41 Figure 1. A History Diagram of Occurrence of Interactions and Recovery Points

* )A13 -0 YX23, /J 01 X23 /2 from Sr entry ------ / +Xi.I X^\/ ^^/^ ^1.^13 7^^\ ^ 7 x 010 -- — r~l 0^/ ^\^ ^.h X12,/A ^2 * o se (0,0, Figure 2. to state (0,0,for 3 Processes0) Figure 2. The Model of Asynchronous RB's for 3 Processes

entry --— _ nn (n -l) 2(n-2)X 2(n-2)X (n-l)X 0 n IL (n -1)C 3 Q Jd 2ju ^n So~ ~A 2^~'(n -l)(n -2)X Figure 3. The Siplified Model of Asynchronous RBs for n Processes Figure 3. The Simplified Model of Asynchronous RB's for n Processes

from state SO z23 */ i ) ^23 -X23 from se' and s6" l — 2 23 3 3 toSaf j\ - l2+13 \ \ from & to S\ PI \ 23 to S4' from S4' and 54" n n n jV= G F. At k.and G E E xij+E k -' C i=j=lj ti =l Figure 4. The Construction of State S2' and S2" of Discrete Markov Chain Yd

CT' p= 1.0 p=1.2 xo LU _J p=O.8 0o [ l l4 4 44 —-I —-— 0p=0:5 t.OO 2.0 00 5.00 6.00 NUMBER OF PROCtSSES (n) p=( ~ Aj)/(SH) Ijlj=.j *i -k=1 X<j =X for all i,j and /l1=2=....=/= 1.0 Figure 5. Mean value of X vs. the number of processes

_ — I~ ~ case 1: (Al,,U2,.^)=(1 0,1.0,1.0), (Xi2,.23S,lX)=(0, 1.0Q,1.0) case 2: (Al,,La,/)=(0.6.0.45.0.45), (Xi2.X23,Xi3)=(0.5,0.5,0.5) case 3: (/l,zl.s^)=(0.6,0.4545), (X12,.X23,X3)=(0757550.750.75) case 1 x LL 0 CD I — U, Z case 3 ": o case 2 ~~oO 040 0TI0 (NORMRL0 1.60 2.00 "Figure 6 TIR (NORt t f D) Figure 6. The Density Function of X, fx,(t)

PI P2 Ps time synchronization request P, -ready P33-redy P22-ready I 1 I synchronization _ request Y2 YI P22T-re ady z jie X L P33-ready I — r1-r^ aD 1:3- - - Pl1 -ready,, Figure 7. Establishment of Recovery Lines upon Synchronization Re quests

PI P2 P3 time 3 RPI is 1 __ _,..______...PRPI'"... —--'" ___....- restart line with respect to PRPxl | the failure of Pa at AT2 implantation request RP RP PR p22 _ P = RP 2 23 E z _'^^?PRP 1 2a RPRP32 AT3 P: Recovery Point (RP): Pseudo Recovery Point (PRP) Note: all occurrences of interactions are omitted Figure 8. Establishment of Pseudo Recovery Points for Rollback Error Recovery

UNIVERSITY OF MICHIGAN illv11 #8i1 Mil il 3 9015 03624 4881 case 1 2 3, 4 5 (pt,ju,p,) (1.0,1.0,1.0) (1.5,1.0,0.5) (1.0,1.0,1.0) (1.5,1.0,0.5) (1.5,1.0,0.5) (XXa,,AXs) (1.0,1.0,1.0) (1.0,1.0,1.0) (1.5,0.5,1.0) (1.5,0.5,1.0) (0.5,1.5,1.0) E(X) 2.598 3.357 2.600 3.203 3.354 E(L 1) 2.500 4.847 2.453 4.533 4.967 E(L2) 2.500 3.231 2.453 3.022 3.111 E(Ls) 2.500 1.616 2.453 1.511 1.656 E(L:+L+L.) 7.500 9.693 7.360 9.065 9.933 Table 1. Mean Values of X and Li for constant p