Geographic quorum system approximations

Paz Carmi, Shlomi Dolev, Sariel Har-Peled, Matthew J. Katz, Michael Segal

Research output: Contribution to journalArticlepeer-review

Abstract

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set Χ of sites in the plane (representing servers) into quorums (i.e., clusters) of size k. The distance between a point p and a cluster C is the Euclidean distance between p and the site in C that is the farthest from p. We present a near linear time constant-factor approximation algorithm for partitioning Χ into clusters, such that the maximal distance between a point in the underlying region and its closest cluster is minimized. Next, we describe a data structure for answering (approximately) nearest-neighbor queries on such a clustering. Finally, we study the problem of partitioning into clusters with an additional load-balancing requirement.

Original languageEnglish (US)
Pages (from-to)233-244
Number of pages12
JournalAlgorithmica (New York)
Volume41
Issue number4
DOIs
StatePublished - Feb 2005

Keywords

  • Clustering
  • Geometric optimization
  • Quorum system

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Geographic quorum system approximations'. Together they form a unique fingerprint.

Cite this