Exploiting Logical Structures to Reduce Quorum Sizes of Replicated Databases

Voting is a traditional mechanism used for maintaining the consistency of replicated data indistributed systems. A significant problem in protocols that use voting is the size of thequorum needed on each access to the replicated data. In this paper, we propose replicacontrol protocols where the synchronization cost is reduced by exploiting the structuralinformation of the underlying system. We also propose a novel logical structure formanaging replicated data, by imposing a logical wheel structure on the set of copies of anobject. The logical structure ensures minimum read quorum size of one, by reading onecopy of an object while guaranteeing fault-tolerance of write operations.