Optimal placements in ring network for data replicas in distributed database with majority voting protocol

Zhao Zhang, Weili Wu, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With majority voting protocol, a location is survived for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. thai uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.

Original languageEnglish (US)
Title of host publicationProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008
Pages387-394
Number of pages8
DOIs
StatePublished - 2008
Event28th International Conference on Distributed Computing Systems, ICDCS 2008 - Beijing, China
Duration: Jul 17 2008Jul 20 2008

Publication series

NameProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008

Other

Other28th International Conference on Distributed Computing Systems, ICDCS 2008
CountryChina
CityBeijing
Period7/17/087/20/08

Keywords

  • Data replica
  • Distributed database
  • Majority voting protocol
  • Ring network

Fingerprint Dive into the research topics of 'Optimal placements in ring network for data replicas in distributed database with majority voting protocol'. Together they form a unique fingerprint.

Cite this