Optimal replica control protocols exhibit symmetric operation availabilities

Replicating data in a distributed system is a suitable means for increasing the availability as well as the performance of data access operations. Unfortunately, there exists a trade-off between these two properties: a replica control protocol which exhibits, e.g., a high read availability and low read operation costs usually suffers from low write availability and high write operation costs. This trade-off is visible for protocols like Weighted Voting for which the above characteristics can be customized by adjusting certain protocol parameters. Changing the read and write quorums of a Weighted Voting protocol while preserving the protocol´s correct behavior increases either the read availability and the write operation costs or the write availability and the read operation costs but not both at the same time. We prove that for a large class of replica control protocols, a certain symmetry between the read and write operation availability exists. We further demonstrate how a protocol without this symmetry property can be optimized such that the resulting protocol has identical cost but a higher read or write availability or both. We present two design strategies which lead to those optimized replica control protocols. By using the well-known Grid Protocol (which lacks symmetry) as an example, we apply our findings to derive two different replica control protocols with superior characteristics.