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.