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