Robustness in replicated databases
Rajiv Ranjan Tewari, Nabil R. Adam · Medical Entomology and Zoology · 1990
Replicated distributed databases store copies of database items at multiple sites to increase availability and response time of transactions. However, replication places a concomitant responsibility on the database system to maintain consistency and serializability of replicated data. Site and communication failures can disrupt the database processing, decreasing the availability of the database. Robustness is the resistance of the database to site and communication link failures, and network partitioning; and is a highly desirable property in systems requiring near real-time response. We consider the general file allocation problem for allocation of file copies to sites in a distributed computing system with nodes and links that have a given probability of failure. This problem is formulated as a non-linear integer programming problem with availability and reliability constraints that model several consistency control protocols. A modified drop-add heuristic solution procedure is proposed and its performance evaluated. Using the file allocation provided by this solution as an input parameter, we develop two robust protocols that provide improved availability while maintaining reliability and consistency of the replicated database. The first protocol assumes serializability as the correctness criteria. The correctness of this protocol is demonstrated using serializability theory for replicated data, both for site failures and communication link failures. The second protocol (merge protocol) relaxes the assumption of serializability as the correctness criteria for replicated databases, and utilizes a property known as eventual serializability. This protocol is proved correct using formal techniques, and the performance of the merge protocol is analyzed by simulation techniques, showing that the merge protocol performs better than previously proposed protocols.