A New Quorum Consensus Method with High Fault-Tolerance for Managing Replicated Data

Xuemin Lin
Department of Computer Science, The University of Western Australia, Nedlands, WA 6907, Australia.
lxue@cs.uwa.oz.au

Abstract

The main objective of data replication in a distributed database system is to proovide high availability of data for transaction processing. Quorum consensus (QC) methods are commonly applied to managing replicated data. In this paper, we present a novel quorum consensus method. The proposed QC method has a low message overhead: 1) In the best case, each transaction operation process needs only to communicate with $O(\sqrt n)$ remote sites to get permission (n is the number of sites storing replicated copies of the manipulating data item). 2) In the worst case, each transaction operation process may be forced to communicate with $O (\sqrt n \log n)$ remote sites. Further, we can show that the proposed QC method is highly fault-tolerant, and fully distributed (i.e., each site in a distributed system bears equal responsibility). We also compare our method to existing QC methods. Conference Home Page