A Technique for Constructing Highly Available Services,
Abstract
This paper describes a general method for constructing a highly-available service for use in a distributed system. It gives a specific implementation of the method and proves the implementation correct. The service presents its clients with a consistent view of its state, but the view may contain old information. Clients can indicate how recent the information must be. The method was invented as a way of optimizing the orphan detection strategy developed for the Argus language and system, but appears to be applicable to a wide range of applications, including garbage collection of objects in a distributed heap, locating movable objects in a distributed system, and deletion of unused versions in a hybrid concurrency control scheme. It requires that applications satisfy certain semantic constraints. For such applications, the method performs better than other replication schemes. The method is intended to be used in an environment in which individual computers, or nodes, are connected by a communications network. Both the nodes and the network may fail; the method tolerates these failures. The nodes are failstop processors; we assume they can crash, but Byzantine failures are not expected. We assume that nodes do eventually recover from crashes, and that each node has access to a stable storage device that (with very high probability) preserves the information entrusted to it. After a crash, a node can recover the portion of its state that was written to its stable storage device before the crash.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1988
- Accession Number
- ADA192544
Entities
People
- Barbara Liskov
- Luiba Shrira
- Rivka Ladin
Organizations
- Massachusetts Institute of Technology