Back to search

University of North Texas

A Highly Fault-Tolerant Distributed Database System with Replicated Data

Abstract

dc:description

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).

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 × 5

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lin, Tsai S. (Tsai Shooumeei). A Highly Fault-Tolerant Distributed Database System with Replicated Data. University of North Texas, 1994. https://digital.library.unt.edu/ark:/67531/metadc278403/