Network reliability and optimal resource allocation in distributed database systems

One of the primary advantages of distributed database systems over traditional centralized databases is increased data availability. By storing multiple copies of data at various sites in the network, a technique known as replication, a distributed database can provide a higher degree of availability when sites or communication links fail. When failures partition the network into isolated components, however, the locations of data determine whether transactions can be successfully executed, and hence the overall availability provided by the system.; This dissertation investigates the problem of placing replicated data in a distributed database system in order to maximize availability in the presence of network failures. Since optimally locating even a single data copy is in general #{dollar}{lcub}cal P{rcub}{dollar}-complete, we focus on several special cases of the optimal placement problem. In Part I, we study networks of arbitrary topology subject to various constraints on communication link failures. We derive necessary properties of optimal placements in networks with small probability of link failure, large probability of link failure, and asynchronous link failures.; In Part II, we analyze the optimal placement problem for distributed databases residing on tree networks. In this research we extend previous work by Stephens, Yesha, and Humenik, and present new results for trees with large probability of link failure, and trees with asynchronous link failures. In both Parts I and II, we formulate the optimality conditions obtained for each case as a graph optimization problem, and develop polynomial algorithms or furnish proofs of {dollar}{lcub}cal NP{rcub}{dollar}-completeness as appropriate.; Part III is devoted to an empirical performance analysis of two heuristics for the optimal placement problem. The Spanning Tree Heuristic, originally proposed by Stephens, Yesha, and Humenik, is shown to find high-availability placements for read transactions in sparse networks. The Eigenvector Heuristic, based on linear-algebra techniques proposed by Matthews for resource placement problem, is shown to find exceptionally high-availability placements for write transactions in networks of varying densities and link failure probabilities.