A tight upper bound on the benefits of replication and consistency control protocols
Donald Barton Johnson, Larry Raab · 1991
We 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 single copy provides availability A for O < A < 1, then no scheme can achieve availabdity greater than ~ in the same network.We show this bound to be the best possible for any network with availabdit y greater than .25.Although, as we prove, the problem of calculating A is #Pcompletej we describe a method for approximating the op timal location for a single copy which adjusts dynamically to current network characteristics.This bound is most useful for high availabilities, which tend to be obtainable with modern networks and their constituent sites and links.