University of North Texas
A Highly Fault-Tolerant Distributed Database System with Replicated Data
Abstract
dc:descriptionBecause of the high cost and impracticality of a high connectivity network, most recent research in transaction processing has focused on a distributed replicated database system. In such a system, multiple copies of a data item are created and stored at several sites in the network, so that the system is able to tolerate more crash and communication failures and attain higher data availability. However, the multiple copies also introduce a global inconsistency problem, especially in a partitioned network. In this dissertation a tree quorum algorithm is proposed to solve this problem, imposing a logical tree structure along with dynamic system reconfiguration on all the copies of each data item. The proposed algorithm can be viewed as a dynamic voting technique which, with the help of an appropriate concurrency control algorithm, exhibits the major advantages of quorum-based replica control algorithms and of the available copies algorithm, so that a single copy is read for a read operation and a quorum of copies is written for a write operation. In addition, read and write quorums are computed dynamically and independently. As a result expensive read operations, like those that require several copies of a data item to be read in most quorum schemes, are eliminated. Furthermore, the message costs of read and write operations are reduced by the use of smaller quorum sizes. Quorum sizes can be reduced to a constant in a lightly loaded system, and log n in a failure-free network, as well as [n +1/2] in a partitioned network in a heavily loaded system. On average, our algorithm requires fewer messages than the best known tree quorum algorithm, while still maintaining the same upper bound on quorum size. One-copy serializability is guaranteed with higher data availability and highest degree of fault tolerance (up to n - 1 site failures).
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 1994
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lin, Tsai S. (Tsai Shooumeei)
- Contributors dc:contributor
-
- Jacob, Roy Thomas
- Vlach, Frank
- Yang, Chao-Chih
- Wu, Frederick H.
- Renka, Robert J.
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Public
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights reserved.
- Lin, Tsai S. (Tsai Shooumeei)
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
call-no: 379 N81d no.4041
untcat: b1839278
local-cont-no: 1002720605-lin
ark: ark:/67531/metadc278403