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