BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR90-157
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Johnson, Donald B.
AUTHOR:: Raab, Larry
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1990
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR90-157.pdf
ABSTRACT::
	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 0 <= A <= 1, then no scheme can
achieve availability greater than sqrt(A) in the same network.  We show
this bound to be the best possible for any network with availability
greater than .25.  Although, as we proved, the problem of calculating
A is #P-complete, we describe a method for approximating the optimal
location for a single copy which adjusts dynamically to current
network characteristcs.  This bound is most useful for high
availabilities, which tend to be obtainable with modern networks and
their constituent components.
END:: ncstrl.dartmouthcs//TR90-157