A Highly Available Paradigm for Consistent Object Replication.

Author: Idit Keidar.

Supervised by: Danny Dolev.

Masters thesis. Institute of Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel, April 1994

Also availbale as Technical Report CS95-5, Institute of Computer Science, The Hebrew University of Jerusalem.


This work provides an efficient paradigm for object replication using the State Machine approach, overcoming network partitions and reconnects. The Consistent Object Replication Layer (COReL) supplies the application builder with long-term services such as reconciliation of states among recovered and reconnected processors and global message ordering. COReL is a high-level communication service layer, designed in the Transis environment. It supplies the services defined for the Replication Service layer in HORUS and Transis.

We present an algorithm for totally ordering messages in the face of network partitions and site failures. The novelty of this algorithm is that it always allows a majority (or quorum) of connected processors in the network to make progress (i.e. totally order messages), if they remain connected for sufficiently long, regardless of past failures. Furthermore, our algorithm always allows processors to initiate messages, even when they are not members of a connected majority component in the network. Thus, messages can eventually become totally ordered even if their initiator is never a member of a majority component. The algorithm orders each message within two communication rounds, if no failures occur during these rounds.

We describe how COReL may be used in the design of distributed and replicated database systems. We present an atomic commitment protocol (ACP) based on COReL. The novelty of this ACP is that it always allows a majority (or quorum) of processors that become connected to resolve the transaction, if they remain connected for sufficiently long. We know of no other ACP with this feature. We suggest a paradigm for replica control, based on COReL, that always allows a majority of connected processors to update the database.

Postscript Version: ps, ps.gz. Israel mirror site: ps.gz.

Last modified: Mon Jul 1 14:33:58 EDT 2002