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 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.

A fundamental problem of distributed system design in an existing network where components can fail is finding an optimal location at which to place a resource. This paper proves exactly how hard this placement problem is under the measure of data availability. Specifically, it shows that the optimal placement problem for availability is #P-complete, a measure of intractability at least as severe as $NP$-completeness. To obtain these results, the environment in which a distributed system operates is modelled by a probabilistic graph, which is a set of fully reliable vertices representing sites and a set of edges representing communication links, each operational with a rational probability. Finding the optimal placement in a probabilistic graph is proved to be #P-complete by giving a sequence of Turing reductions from #Satisfiability. This result is generalized to networks in which each site and each link has an independent, rational operational probability and to networks in which all the sites or all the links have fixed, uniform operational probabilities. Given the anticipated computational difficulty of finding an exact solution, the requirements for effective, practical approximation methods are discussed.

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.