×

zbMATH — the first resource for mathematics

Optimal inter-object correlation when replicating for availability. (English) Zbl 1267.68109
Summary: Data replication is a key technique for ensuring data availability. Traditionally, researchers have focused on the availability of individual objects, even though user-level tasks (called operations) typically request multiple objects. Our recent experimental study has shown that the assignment of object replicas to machines results in subtle yet dramatic effects on the availability of these operations, even though the availability of individual objects remains the same. This paper is the first to approach the assignment problem from a theoretical perspective, and obtains a series of results regarding assignments that provide the best and the worst availability for user-level operations. We use a range of techniques to obtain our results, from standard combinatorial techniques and hill climbing methods to Janson’s inequality (a strong probabilistic tool). Some of the results demonstrate that even quite simple versions of the assignment problem can have surprising answers.

MSC:
68P20 Information storage and retrieval of data
68M14 Distributed systems
Software:
Chord
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adya, A., Bolosky, W.J., Castro, M., Cermak, G., Chaiken, R., Douceur, J.R., Howell, J., Lorch, J.R., Theimer, M., Wattenhofer, R.P.: FARSITE: federated, available, and reliable storage for an incompletely trusted environment. In: USENIX OSDI (2002)
[2] Alon N., Spencer J.H.: The probabilistic method. Wiley, New York (2000) · Zbl 0996.05001
[3] Bolosky, W.J., Douceur, J.R., Ely, D., Theimer, M.: Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs. In: ACM SIGMETRICS (2000)
[4] Dabek, F., Kaashoek, M.F., Karger, D., Morris, R., Stoica, I.: Wide-area cooperative storage with CFS. In: ACM SOSP (2001)
[5] Douceur, J.R., Wattenhofer, R.P.: Competitive hill-climbing strategies for replica placement in a distributed file system. In: DISC (2001) · Zbl 1024.68510
[6] Ghemawat, S., Gobioff, H., Leung, S.T.: The google file system. In: ACM SOSP (2003)
[7] Haeberlen, A., Mislove, A., Druschel, P.: Glacier: highly durable, decentralized storage despite massive correlated failures. In: USENIX NSDI (2005)
[8] Janson S.: Poisson approximations for large deviations. Random Struct Algorithm 1, 221–230 (1990) · Zbl 0747.05079 · doi:10.1002/rsa.3240010209
[9] Janson, S., Luczak, T., Rucinski, A.: An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In: Karo’nski, M., Jaworski, J., Ruci’nski, A. (eds.) Random Graphs’87. Wiley, New York (1990)
[10] Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahy, R.: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. In: ACM STOC (1997) · Zbl 0963.68012
[11] Kistler J., Satyanarayanan M.: Disconnected operation in the coda file system. ACM Trans. Comput. Syst. 10(1), 3–25 (1992) · doi:10.1145/146941.146942
[12] Knuth D.E.: The Art of Computer Programming, vol 1. Addison Wesley, Reading (1997) · Zbl 0895.68055
[13] Kubiatowicz, J., Bindel, D., Chen, Y., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C., Zhao, B.: OceanStore: an architecture for global-scale persistent storage. In: ACM ASPLOS (2000)
[14] Pang, J., Gibbons, P.B., Kaminsky, M., Seshan, S., Yu, H.: Defragmenting DHT-based distributed file systems. In: Proceedings of International Conference on Distributed Computing Systems (2007)
[15] Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: ACM SIGCOMM (2001) · Zbl 1060.68544
[16] Ratnasamy, S., Karp, B., Shenker, S., Estrin, D., Govindan, R., Yin, L., Yu, F.: Data-centric storage in sensornets with GHT: a geographic hash table. Mobile Netw. Appl. 8(4), 427–442 (2003)
[17] van Renesse, R., Schneider, F.B.: Chain replication for supporting high throughput and availability. In: USENIX OSDI (2004)
[18] Rowstron, A., Druschel, P.: Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems. In: ACM Middleware (2001) · Zbl 1051.68788
[19] Santos, J., Muntz, R., Ribeiro-Neto, B.: Comparing random data allocation and data striping in multimedia serviers. In: ACM SIGMETRICS (2000)
[20] Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. In: ACM SIGCOMM (2001)
[21] Szalay, A., Kunszt, P., Thakar, A., Gray, J., Slutz, D.: Designing and mining multi-terabyte astronomy archives: the sloan digital sky survey. In: ACM SIGMOD (2000)
[22] TPC Benchmark. http://www.tpc.org/
[23] Valiant L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979) · Zbl 0419.68082 · doi:10.1137/0208032
[24] Yu, H., Gibbons, P.B., Nath, S.: Availability of multi-object operations. In: USENIX NSDI (2006)
[25] Yu, H., Vahdat, A.: Minimal replication cost for availability. In: ACM PODC (2002) · Zbl 1292.68020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.