OPTIMAL AVAILABILITY QUORUM SYSTEMS - THEORY AND PRACTICE

Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are useful f or distributed and replicated databases, name servers, mutual exclusio n, and distributed access control and signatures. The un-availability of a quorum system is the probability of the event that no live quorum exists in the system. When such an event occurs the service is comple tely halted. The un-availability is widely accepted as the measure by which quorum systems are evaluated. In this paper we characterize the optimal availability quorum system in the general case, when the failu re probabilities may take any value in the range 0 < p(i) < 1. Then we deal with the practical scenario in which the failure probabilities a re unknown, but can be estimated. We give a robust and efficient algor ithm that calculates a near optimal quorum system based on the estimat ed failure probabilities. (C) 1998 Elsevier Science B.V.