Because 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).
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc278403 |
| Date | 12 1900 |
| Creators | Lin, Tsai S. (Tsai Shooumeei) |
| Contributors | Jacob, Roy Thomas, Vlach, Frank, Yang, Chao-Chih, Wu, Frederick H., Renka, Robert J. |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | iv, 106 leaves : ill., Text |
| Rights | Public, Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved., Lin, Tsai S. (Tsai Shooumeei) |
Page generated in 0.002 seconds