Geographic Quorum System Approximations | Algorithmica
Skip to main content
Springer Nature Link
Log in

Geographic Quorum System Approximations

  • Published:
Algorithmica Aims and scope Submit manuscript

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 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 partitioning X 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, , Israel

    Paz Carmi, Shlomi Dolev & Matthew J. Katz

  2. Department of Computer Science, DCL 2111, University of Illinois, 1304 West Springfield Ave., Urbana, IL 61801, , USA

    Sariel Har-Peled

  3. Department of Communication Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel

    Michael Segal

Authors
  1. Paz Carmi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shlomi Dolev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sariel Har-Peled
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Matthew J. Katz
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Michael Segal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

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

Rights and permissions

Reprints and permissions

About this article

Cite this article

Carmi, P., Dolev, S., Har-Peled, S. et al. Geographic Quorum System Approximations. Algorithmica 41, 233–244 (2005). https://doi.org/10.1007/s00453-004-1130-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-004-1130-1

Search

Navigation