Quorum placement in networks: Minimizing network congestion

Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing 2006
Pages16-25
Number of pages10
StatePublished - 2006
Event25th Annual ACM Symposium on Principles of Distributed Computing 2006 - Denver, CO, United States
Duration: Jul 23 2006Jul 26 2006

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume2006

Conference

Conference25th Annual ACM Symposium on Principles of Distributed Computing 2006
Country/TerritoryUnited States
CityDenver, CO
Period7/23/067/26/06

Keywords

  • Approximation algorithms
  • Congestion Problems
  • LP Rounding
  • Quorum Systems

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Quorum placement in networks: Minimizing network congestion'. Together they form a unique fingerprint.

Cite this