BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR90-158
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Finding Optimal Quorum Assigments for Distributed Databases
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-158.pdf
ABSTRACT::
	Replication has been studied as a method of increasing the
availability of a data item in a distributed database subject to
component failures and consequent partitioning.  The potential for
partitioning requires that a protocol be employed which guarantees
that any access to a data item is aware of the most recent update to
that data item.  By minimizing the number of access requests denied
due to this constraint, we maximize availability.  In the event that
all access requests are reads, placing one copy of the data item at
each site clearly leads to maximum availability.  The other extreme,
all access requests are write requests or are treated as such, has
been studied extensively in the literature.  In this paper we
investigate the performance of systems with both read and write
requests.  We describe a distributed on-line algorithm for determining
the optimal parameters, or optimal quorum assignments, for a commonly
studied protocol, the quorum consensus protocol[9].  We also show how
to incorporate these optimization techniques into a dynamic quorum
reassignment protocol.  In addition, we demonstrate via simulation
both the value of this algorithm and the effect of various read-write
rations on availability.  This simulation, on 101 sites and up to 5050
links(fully- connected), demonstrates that the techniques described
here can greatly increase data availability, and that the best quorum
assignments are frequently realized at the extreme values of the
quorum parameters.
END:: ncstrl.dartmouthcs//TR90-158