Missing-partition dynamic voting scheme for replicated database systems

Abstract

A replication control protocol utilizing dynamic voting is presented for ensuring database correctness so that the system behaves like a one-copy database to the users. The protocol dynamically adjusts vote assignment of data items in response to failures and recoveries, thus maintaining higher data availability than static voting schemes in the event of network partitioning. Unlike existing dynamic voting schemes, it supports inexpensive read operations which access one copy, rather than all copies, of each data item read. Since read operations outnumber write operations in most applications, this protocol enjoys better performance. With this protocol, transactions run in one of three modes: normal mode, missing-partition mode, or psuedo-normal mode. Because a partition number and a last current copy cardinality are associated with each copy, read operations only require reading one copy of a data item when run in the normal mode.