A Tight Upper Bound on the Benefits of Replica Control Protocols

AbstractWe present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning. The bound is presented in terms of the performance of a single resource in the same network. The bound is tight and is the first such bound known to us. Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication. We show that if a well-placed single copy provides availability A for 0 ≤ A ≤ 1, then no scheme can achieve availability greater than √A in the same network. We show this bound to be the best possible for any network with availability greater than 0.25. We also prove that the problem of calculating A is #P-complete and describe a method for approximating the optimal location for a single copy which adjusts dynamically to current network characteristics. The bound presented here is most useful for high availabilities, which tend to be obtainable with modern networks and their constituent sites and links