Accession Number:

ADA200985

Title:

Viewstamped Replication for Highly Available Distributed Systems

Descriptive Note:

Doctoral thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1988-08-01

Pagination or Media Count:

103.0

Abstract:

This dissertation presents viewstamped replication, a new algorithm for the implementation of highly available computer services that continue to be usable in spite of node crashes and network partitions. Our goal is to design an efficient mechanism that makes it easy for programmers to implement these services without complicating the programming model. Our replication method is based on a primary copy technique, where one replica is the primary and others are backups, and is integrated into the fabric of an atomic transaction mechanism. Transactions are run only at the primary and need not involve the backups the primary propagates the effects of transaction processing to the backups in the background. The method exhibits low delay during normal operation, has low overhead, and increases the likelihood that transactions will commit in spite of failures. When failures occur, replicas are reorganized automatically and a new primary is selected if the old one becomes inaccessible. This reorganized automatically and a new primary is selected if the old one becomes inaccessible. This reorganization is called a view change and is accomplished by a view management algorithm. Since the primary only communicates with the backups in background mode, the effects of some processing may be lost after a view change the affected transactions must abort. If the effects are known at the new primary, then no information is lost and the transaction can commit. Furthermore, if transactions commit, we guarantee that their effects are not lost. A special kind of timestamp, called a viewstamp, allows the algorithm to distinguish these cases inexpensively. Keywords Fault-tolerance, Distributed computer systems.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE