Reliability of Replicated Data Objects

Improved fault tolerance of many applications can be achieved by replicating data at several sites. This data redundancy requires a protocol to maintain the consistency of the data object in the presence of site failures. The most commonly used scheme is voting. Voting and its variants are unaected by network partitions. When network partitions cannot occur, better performance can be achieved with the available copy scheme. Common measures of dependability include reliability, which is the probability that a replicated object will remain constantly available over a xed time period, and availability, which is the steady-state probability that the object is available at any given moment. Availability has received much attention, in part because its analysis is more tractable than that of reliability. However, reliability is the most important performance measure for systems that cannot tolerate any failures. We investigate the reliability of replicated data objects managed by voting, avail-able copy and their variants. Where possible, closed-form expressions for the reli-ability of the various consistency protocols are derived using standard Markovian assumptions. In other cases, numerical solutions are found and validated with sim-ulation results. The results are contrasted with the relative availabilities of the systems, showing that an increase in reliability implies an increase in availability.