Abstract
In a distributed database system, data replicas are placed at different locations of a network to achieve the high data availability in presence of link failure. Optimal placements of data replicas have been studied extensively in the literature for various protocol. In this paper, we present a sufficient and necessary condition for optimality of a placement of odd number of data replicas in a ring network with majority voting protocol. As a corollary, we give a proof of a recent conjecture of Hu et al. (manuscript, 1999). Moreover, we also give a simple algorithm to find optimal placements in tree network with majority voting protocol.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 555-571 |
| Number of pages | 17 |
| Journal | Theoretical Computer Science |
| Volume | 258 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - 2001 |
Bibliographical note
Funding Information:This work is supported in part by the Army High Performance Computing Research Center under the auspices of Department of the Army, Army Research Laboratory Cooperative agreement number DAAH04-95-2-0003=contract number DAAH04-95-C-0008, the content of which does not necessarily reCect the position or the policy of the government, and no o4cial endorsement should be infe rred. This work is also supported in part by the National Science Foundation under grant 9631539. ∗Corresponding author. E-mail addresses: [email protected] (S. Shekhar), [email protected] (W. Wu).
Keywords
- Cycle and tree
- Distributed database
- Majority voting protocol
- Optimal placement of data replicas