Increasing the Resilience of Distributed and Replicated Database Systems.

Authors: Idit Keidar and Danny Dolev.

In the Journal of Computer and System Sciences (JCSS) special issue with selected papers from PODS 1995, 57(3) pages 309-324. December 1998.


This paper presents a new atomic commitment protocol, enhanced three phase commit (E3PC), that always allows a quorum in the system to make progress. Previously suggested quorum-based protocols (e.g., the quorum-based three phase commit (3PC) (Skeen, 1982)) allow a quorum to make progress in case of one failure. If failures cascade, however, and the quorum in the system is ``lost'' (i.e., at a given time no quorum component exists), a quorum can later become connected and still remain blocked. With our protocol, a connected quorum never blocks. E3PC is based on the quorum-based 3PC, and it does not require more time or communication than 3PC. We describe how this protocol can be exploited in a replicated database setting, making the database always available to a majority of the sites.

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

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