TY - GEN
T1 - Bandwidth-limited optimal deployment of eventually-serializable data services
AU - Michel, Laurent
AU - Van Hentenryck, Pascal
AU - Sonderegger, Elaine
AU - Shvartsman, Alexander
AU - Moraal, Martijn
PY - 2009
Y1 - 2009
N2 - Providing consistent and fault-tolerant distributed object services is among the fundamental problems in distributed computing. To achieve fault-tolerance and to increase throughput, objects are replicated at different networked nodes. However, replication induces significant communication costs to maintain replica consistency. Eventually-Serializable Data Service (ESDS) has been proposed to reduce these costs and enable fast operations on data, while still providing guarantees that the replicated data will eventually be consistent. This paper revisits ESDS instances where bandwidth constraints are imposed on segments of the network interconnect. This class of problems was shown to be extremely challenging for both Mixed Integer Programming (MIP) and for Constraint Programming (CP), some instances requiring hours of computation time. The paper presents an improved constraint programming model, a constraint-based local search model that can obtain high-quality solutions quickly and a local search/constraint programming hybrid. The experimental results indicate that the resulting models significantly improve the state of the art.
AB - Providing consistent and fault-tolerant distributed object services is among the fundamental problems in distributed computing. To achieve fault-tolerance and to increase throughput, objects are replicated at different networked nodes. However, replication induces significant communication costs to maintain replica consistency. Eventually-Serializable Data Service (ESDS) has been proposed to reduce these costs and enable fast operations on data, while still providing guarantees that the replicated data will eventually be consistent. This paper revisits ESDS instances where bandwidth constraints are imposed on segments of the network interconnect. This class of problems was shown to be extremely challenging for both Mixed Integer Programming (MIP) and for Constraint Programming (CP), some instances requiring hours of computation time. The paper presents an improved constraint programming model, a constraint-based local search model that can obtain high-quality solutions quickly and a local search/constraint programming hybrid. The experimental results indicate that the resulting models significantly improve the state of the art.
UR - http://www.scopus.com/inward/record.url?scp=69849107172&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69849107172&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-01929-6_15
DO - 10.1007/978-3-642-01929-6_15
M3 - Conference contribution
AN - SCOPUS:69849107172
SN - 3642019285
SN - 9783642019289
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 193
EP - 207
BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 6th International Conference, CPAIOR 2009, Proceedings
T2 - 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009
Y2 - 27 May 2009 through 31 May 2009
ER -