Harary Networks: Connectivity for Highly Available Real-Time Distributed Databases

Shah, Amitabh; Marzullo, Keith

Harary Networks: Connectivity for Highly Available Real-Time Distributed Databases

Abstract

A methodology, called network designing by the desirable partition, for designing Underlying communication networks for distributed databases is proposed. It exploits the fact that in most real-life databases, the data is not fully replicated, and the transactions access pattern is highly local. The methodology consists of identifying a desirable partition of the sites based on the notion of dependencies between sites; the latter is defined by the replication of data and the transaction data access patterns. A hierarchical communication network, called a Harary Network, is then constructed for the identified partition. The notion of desirability takes into account the cost of connection, and thus provides the most desirable construction for a given cost. The method is probabilistic in the sense that in presence of failures, the probability of the occurrence of the desirable partition is higher than that of all other partitions; this results in very high expected availability. It is shown that for most intuitive formulations of the problem, finding the most desirable partition is NP-Hard. However, good and often optimal approximation algorithms exist for this problem. The methodology is particularly suited for designing communication support for real-time distributed databases.

Date Issued

1990-01

Publisher

Cornell University

Keywords

computer science; technical report

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1070

Types

technical report