Team for Research in
Ubiquitous Secure Technology

Citation
D. Golovin, A. Gupta, B.M. Maggs, F. Oprea, M. Reiter. "Quorum placement in networks: Minimizing network congestion". Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, 16–25, June, 2006.

Abstract
A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe reside on the nodes of a physical network and the participating nodes access the system by contacting every element in some quorum, potentially causing the added network congestion induced by these quorum accesses to play a limiting factor in the performance of the algorithm. In this paper we initiate the study of algorithms to place universe elements on the nodes of a physical network so as to minimize the network congestion that results from quorum accesses, while also ensuring that no physical node is overloaded by access requests from clients. We consider two models, one in which communication routes can be chosen arbitrarily and one in which they are fixed in advance. We show that in either model, the optimal congestion (with respect to the load constraints) cannot be approximated to any factor (unless P=NP). However, we show that at most doubling the load on nodes allows us to achieve a congestion that is close to this optimal value. We also shed some light on the extent to which element migration can reduce congestion in this context.

Categories and Subject Descriptors: C.2.4 [Computer- Communication Networks]: Distributed Systems - distributed applications

General Terms: Algorithms, Performance, Theory.

Keywords: Quorum Systems, Congestion Problems, Approximation Algorithms, LP Rounding.

Electronic downloads

• HTML

  D. Golovin, A. Gupta, B.M. Maggs, F. Oprea, M. Reiter. <a
  href="http://www.truststc.org/pubs/140.html"
  >Quorum placement in networks: Minimizing network
  congestion</a>, Proceedings of the 25th ACM Symposium
  on Principles of Distributed Computing, 16–25, June,
  2006.

• Plain text

  D. Golovin, A. Gupta, B.M. Maggs, F. Oprea, M. Reiter.
  "Quorum placement in networks: Minimizing network
  congestion". Proceedings of the 25th ACM Symposium on
  Principles of Distributed Computing, 16–25, June,
  2006.

• BibTeX

  @inproceedings{GolovinGuptaMaggsOpreaReiter06_QuorumPlacementInNetworksMinimizingNetworkCongestion,
      author = {D. Golovin and A. Gupta and B.M. Maggs and F.
                Oprea and M. Reiter},
      title = {Quorum placement in networks: Minimizing network
                congestion},
      booktitle = {Proceedings of the 25th ACM Symposium on
                Principles of Distributed Computing},
      pages = {16–25},
      month = {June},
      year = {2006},
      abstract = {A quorum system over a universe of logical
                elements is a collection of subsets (quorums) of
                elements, any two of which intersect. In numerous
                distributed algorithms, the elements of the
                universe reside on the nodes of a physical network
                and the participating nodes access the system by
                contacting every element in some quorum,
                potentially causing the added network congestion
                induced by these quorum accesses to play a
                limiting factor in the performance of the
                algorithm. In this paper we initiate the study of
                algorithms to place universe elements on the nodes
                of a physical network so as to minimize the
                network congestion that results from quorum
                accesses, while also ensuring that no physical
                node is overloaded by access requests from
                clients. We consider two models, one in which
                communication routes can be chosen arbitrarily and
                one in which they are fixed in advance. We show
                that in either model, the optimal congestion (with
                respect to the load constraints) cannot be
                approximated to any factor (unless P=NP). However,
                we show that at most doubling the load on nodes
                allows us to achieve a congestion that is close to
                this optimal value. We also shed some light on the
                extent to which element migration can reduce
                congestion in this context. <p><b>Categories and
                Subject Descriptors</b>: C.2.4 [Computer-
                Communication Networks]: Distributed Systems -
                distributed applications <p><b>General Terms</b>:
                Algorithms, Performance, Theory.
                <p><b>Keywords</b>: Quorum Systems, Congestion
                Problems, Approximation Algorithms, LP Rounding. },
      URL = {http://www.truststc.org/pubs/140.html}
  }
  

Posted by Christopher Brooks on 17 Nov 2006.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.