Minimal replication cost for availability

ABSTRACT

Today, the utility of many replicated Internet services is limited by availability rather than raw performance. To better understand the effects of replica placement on availability, we propose the problem of minimal replication cost for availability. Let replication cost be the cost associated with replica deployment, dynamic replica creation and teardown at n candidate locations. Given client access patterns, replica failure patterns, network partition patterns, a required consistency level and a target level of availability, the minimal replication cost is the lower bound on a system's replication cost. Solving this problem also answers the dual question of optimal availability given a constraint on replication cost.We design the first algorithm we are aware of to solve the problem, through reduction to integer linear programming and enumeration of pruned serialization orders. Using practical faultloads and workloads, we demonstrate that the exponential complexity of our algorithm is tractable for practical problems with hundreds of candidate locations. The lower bound computed by our algorithm is tight, but the tightness can be sacrificed by a proposed optimization for large problems. We also show that with low replica creation and teardown costs, the bound is close to tight in practical problems even with the optimization.

REFERENCES

• 1: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• 2: B. R. Badrinath , Krithi Ramamritham, Semantics-based concurrency control: beyond commutativity, ACM Transactions on Database Systems (TODS), v.17 n.1, p.163-199, March 1992 [doi>10.1145/128765.128771]
• 3: Daniel Barbara , Hector Garcia-Molina, The vulnerability of vote assignments, ACM Transactions on Computer Systems (TOCS), v.4 n.3, p.187-213, Aug. 1986 [doi>10.1145/6420.6421]
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 6: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 7: Bharat Chandra, Mike Dahlin, Lei Gao, and Amol Nayate. End-to-End WAN Service Availability. In Proceedings of the 3rd Usenix Symposium on Internet Technologies and Systems, January 2001.
• 8: ClarkNet Server Traces. http://ita.ee.lbl.gov/html/contrib/ClarkNet-HTTP.html.
• 9: Brian A Coan , Brian M Oki , Elliot K Kolodner, Limitations on database availability when networks partition, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.187-194, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10606]
• 10: John R. Douceur , Roger Wattenhofer, Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System, Proceedings of the 15th International Conference on Distributed Computing, p.48-62, October 03-05, 2001
• 11: John Hennessy, The Future of Systems Research, Computer, v.32 n.8, p.27-33, August 1999 [doi>10.1109/2.781631]
• 12: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 13: Donald B. Johnson , Larry Raab, A tight upper bound on the benefits of replication and consistency control protocols, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.75-81, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113420]
• 14: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Placement algorithms for hierarchical cooperative caching, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 17-19, 1999, Baltimore, Maryland, United States
• 15: Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance: a technique for increasing concurrency in a replicated system, ACM Transactions on Database Systems (TODS), v.19 n.4, p.586-625, Dec. 1994 [doi>10.1145/195664.195670]
• 16: B. Li, M. Golin, G. Italiano, and A. K. Sohraby. On The Optimal Placement of Web Proxies in the Internet. In Proceedings of IEEE INFOCOM'99, March 1999.
• 17: K. Marzullo and F. Schmuck. Supplying high availability with a standard network file system. In Proceedings of the 8th International Conference on Distributed Computing Systems (ICDCS), 1988.
• 18: Daniel L. McCue and Mark C. Little. Computing replica placement in distributed systems. In Workshop on the Management of Replicated Data, 1992.
• 19: NASA Kennedy Space Center Server Traces. http://ita.ee.lbl.gov/html/contrib/NASA-HTTP.html.
• 20: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 21: Lili Qiu, Venkata Padmanabahn, and Geoffrey Voelker. On the Placement of Web Server Replicas. In Proceedings of the INFOCOM 2001 - Twentieth Annual Joint Conference of the IEEE Computer And Communications Societies, April 2001.
• 22: A. Rosenthal. Computing the Reliability of a Complex Network. SIAM Journal of Applied Mathematics, 32:384-393, 1977.
• 23: J.B. Rothnie and N. Goodman. A Survey of Research adn Development in Distributed Database Systems. In Proceedings of the 3rd International Conference on Very Large Databases, October 1977.
• 24: Aman Singla , Umakishore Ramachandran , Jessica Hodgins, Temporal notions of synchronization and consistency in Beehive, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.211-220, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258513]
• 25: Arun Venkataramani , Phoebe Weidmann , Mike Dahlin, Bandwidth constrained placement in a WAN, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.134-143, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384002]
• 26: Haifeng Yu , Amin Vahdat, The costs and limits of availability for replicated services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 27: Haifeng Yu and Amin Vahdat. Minimal Replication Cost for Availability. Technical Report CS-2002-04, Duke University, Computer Science Department, Durham, NC, 2002. Available at http://www.cs.duke.edu/~yhf/podc02tr.pdf.
• 28: Haifeng Yu , Amin Vahdat, Design and evaluation of a conit-based continuous consistency model for replicated services, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.239-282, August 2002 [doi>10.1145/566340.566342]
• 29: Ellen W. Zegura , Kenneth L. Calvert , Michael J. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.770-783, Dec. 1997 [doi>10.1109/90.650138]