Home Bookmarks Papers Blog

Geographic Quorum Systems Approximations

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

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider \emph{geographic quorum systems}; a geographic quorum system is a partitioning of a set P of points 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 farthest point in \C. We present a near linear time constant-factor approximation algorithm for partitioning P 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 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.

Postscript, PDF.

To appear in Algorithmica.
Last modified: Wed Oct 13 11:40:18 CDT 2004