The Quorum Deployment Problem
Quorum systems are commonly used to maintain the consistency of replicated data in adistributed system. Much research has been devoted to developing quorum systems with good theoreticalproperties, such as fault tolerance and high availability. However, even given a theoreticallygood quorum system, i...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30415 |
| _version_ | 1826208605066493952 |
|---|---|
| author | Gilbert, Seth Malewicz, Grzegorz |
| author2 | Theory of Computation |
| author_facet | Theory of Computation Gilbert, Seth Malewicz, Grzegorz |
| author_sort | Gilbert, Seth |
| collection | MIT |
| description | Quorum systems are commonly used to maintain the consistency of replicated data in adistributed system. Much research has been devoted to developing quorum systems with good theoreticalproperties, such as fault tolerance and high availability. However, even given a theoreticallygood quorum system, it is not obvious how to efficiently deploy such a system in a real network. Thispaper introduces a new combinatorial optimization problem, the Quorum Deployment Problem, andstudies its complexity. We demonstrate that it is NP-hard to approximate the Quorum DeploymentProblem 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 withmetric cost. We begin to study algorithms for variants of the problem. Some variants can be solved optimallyin polynomial time and some NP-hard variants can be approximated to within a constant factor. |
| first_indexed | 2024-09-23T14:08:15Z |
| id | mit-1721.1/30415 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:08:15Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304152019-04-12T08:26:03Z The Quorum Deployment Problem Gilbert, Seth Malewicz, Grzegorz Theory of Computation Quorum systems are commonly used to maintain the consistency of replicated data in adistributed system. Much research has been devoted to developing quorum systems with good theoreticalproperties, such as fault tolerance and high availability. However, even given a theoreticallygood quorum system, it is not obvious how to efficiently deploy such a system in a real network. Thispaper introduces a new combinatorial optimization problem, the Quorum Deployment Problem, andstudies its complexity. We demonstrate that it is NP-hard to approximate the Quorum DeploymentProblem 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 withmetric cost. We begin to study algorithms for variants of the problem. Some variants can be solved optimallyin polynomial time and some NP-hard variants can be approximated to within a constant factor. 2005-12-19T23:27:35Z 2005-12-19T23:27:35Z 2004-10-29 MIT-CSAIL-TR-2004-069 MIT-LCS-TR-972 http://hdl.handle.net/1721.1/30415 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 20 p. 25684763 bytes 1002668 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Gilbert, Seth Malewicz, Grzegorz The Quorum Deployment Problem |
| title | The Quorum Deployment Problem |
| title_full | The Quorum Deployment Problem |
| title_fullStr | The Quorum Deployment Problem |
| title_full_unstemmed | The Quorum Deployment Problem |
| title_short | The Quorum Deployment Problem |
| title_sort | quorum deployment problem |
| url | http://hdl.handle.net/1721.1/30415 |
| work_keys_str_mv | AT gilbertseth thequorumdeploymentproblem AT malewiczgrzegorz thequorumdeploymentproblem AT gilbertseth quorumdeploymentproblem AT malewiczgrzegorz quorumdeploymentproblem |