Voting with Witnesses: A Constistency Scheme for Replicated Files.
J.-F. Paris · International Conference on Distributed Computing Systems · 1986
Voting schemes ensure the consistency of replicated files by disallowing all read and write requests that cannot collect an appropriate quorum of copies. This procedure requires a minimum number of three copies to be of any practical use and tends to disallow a relatively high number of read and write requests. We propose to replace some of these copies by mere records of the current state of the file. These records, called witnesses, will be assigned weights and participate to the collection of quorums. We show, that under very general assumptions, the reliability of a replicated file consisting ofn copies andm witnesses is the same as the reliability of a replicated file consisting of n + m copies. We also compare the availability of a replicated file consisting of two copies and one witness with that of a file having three copies and show that, under normal circumstances, the two files have similar availabilities.