Geographic quorum system approximations Academic Article uri icon


  • Quorum systems are a mechanism for obtaining fault-tolerance and ecient dis- tributed systems. We consider geographic quorum systems; a geographic quorum sys- tem is a partition of a set X 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 parti- tioning X into clusters, such that, the maximal distance between a point in the under- lying 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 describe constant-factor approximation algorithms that associate regions of equal area to the servers in a given set of servers. Two cost measures are considered: the maximum distance of a point to its corresponding server, and the sum of average distances to the servers.

publication date

  • January 1, 2005