LCS Publication Details
Publication Title: The Quorum Deployment Problem
Publication Author: Gilbert, Seth
Additional Authors: Grzegorz Malewicz
LCS Document Number: MIT-LCS-TR-972
Publication Date: 10-29-2004
LCS Group: Theory of Computation
Additional URL:
Abstract:
Quorum systems are commonly used to maintain the consistency of replicated data in a distributed system. Much research has been devoted to developing quorum systems with good theoretical properties, such as fault tolerance and high availability. However, even given a theoretically good quorum system, it is not obvious how to efficiently deploy such a system in a real network. This paper introduces a new combinatorial optimization problem, the Quorum Deployment Problem, and studies its complexity. We demonstrate that it is NP-hard to approximate the Quorum Deployment Problem within any factor of n?, where n is the number of nodes in the distributed network and ? > 0. The problem is NP-hard in even the simplest possible distributed network: a one-dimensional line with metric cost. We begin to study algorithms for variants of the problem. Some variants can be solved optimally in polynomial time and some NP-hard variants can be approximated to within a constant factor.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.