Optimal placement of data replicas in distributed database with majority voting protocol (Q5941207)

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 \textit{X.-D. Hu, H.-J. Huang, X. H.Jia} and \textit{D.-Y. Li} [Placement of data replicas for optimal data availability in ring networks,manuscript (1999)]. Moreover, we also give a simple algorithm to find optimal placements in tree network with majority voting protocol.