@inproceedings{30b529b873c94df3a47b4df07fd4ed84,

title = "Quorum placement in networks to minimize access delays",

abstract = "A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, data replication, and dissemination of information. However, accessing spread-out quorums causes access delays that we would like to minimize. Furthermore, every member of the quorum incurs processing load to handle quorum accesses by clients. In this paper we study the problem of placing quorums in a physical network so as to minimize the delay that clients incur by accessing quorums, and while respecting each physical node's capacity (in terms of the load of client requests it can handle). We provide approximation algorithms for this problem for two natural measures of delay (the max-delay and total-delay). All our algorithms ensure that each node's load is within a constant factor of its capacity, and minimize delay to within a constant factor of the optimal delay for all capacity-respecting solutions. We also provide better approximations for several well-known quorum systems.",

keywords = "Approximation Algorithms, LP Rounding, Location Problems, Quorum Systems",

author = "Anupam Gupta and Maggs, {Bruce M.} and Florian Oprea and Reiter, {Michael K.}",

year = "2005",

doi = "10.1145/1073814.1073829",

language = "English (US)",

isbn = "1581139942",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "87--96",

booktitle = "Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005",

address = "United States",

note = "24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 ; Conference date: 17-07-2005 Through 20-07-2005",

}