Viewstamped Replication for Highly Available Distributed Systems

Download: pdf, ps .

“Viewstamped Replication for Highly Available Distributed Systems” by Brian Oki. Ph.D. dissertation, MIT, Aug. 1988. Also as Technical Report MIT-LCS-TR-423.

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

Download: pdf, ps .

BibTeX entry:

@phdthesis{oki88phd,
   author = {Brian Oki},
   title = {Viewstamped Replication for Highly Available Distributed Systems},
   school = {MIT},
   type = {{Ph.D.}},
   month = aug,
   year = {1988},
   note = {Also as Technical Report MIT-LCS-TR-423}
}

Back to PMG VR publications .

Programming Methodology Group