Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols
Donald B. Johnson, Larry Raab
Dartmouth PCS-TR90-157


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.


Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Donald B. Johnson and Larry Raab, "A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols." Dartmouth Computer Science Technical Report PCS-TR90-157, 1990.

Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.