Browse Prior Art Database

ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT PROCESSES WITH RECOVERY BLOCKS

IP.com Disclosure Number: IPCOM000128448D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Y-H. Lee: AUTHOR [+4]

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT PROCESSES WITH RECOVERY BLOCKS

KG. Shin

Y-H. Lee
CRL-TR-9-83

FEBRUARY 1983

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

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.

1 This 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.

University of Michigan Computing Research Laboratory Page 1 Feb 01, 1983

Page 2 of 13

ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT PROCESSES WITH RECOVERY BLOCKS

TABLE OF CONTENTS

1. INTRODUCTION.....2
2. EVALUATION OF ASYNCHRONOUS RECOVERY BLOCKS.....5
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
5. CONCLUSION.....16
ACKNOWLEDGEMENT.....18
REFERENCES..... ANALYSIS OF BACKWARD ERROR RECOVERY FOR CONCURRENT
PROCESSES WITH RECOVERY BLOCKS2 Kang G. Shin and Yann-Hang Lee Computing Research Laboratory
Department of Electrical and Computer Engineering The University of Michigan
Ann Arbor, Michigan 48109

1. INTRODUCTION

Recent advances in V...