Optimal inter-object correlation when replicating for availability

Data replication is a key technique for ensuring data availability. Traditionally, researchers have focused on the availabili ty of indi- vidual objects, even though user-level tasks (called operations) typ- ically request multiple objects. Our recent experimental s tudy has shown that the assignment of object replicas to machines results in subtle yet dramatic effects on the availability of these ope rations, even though the availability of individual objects remains the same. This paper is the first to approach the assignment problem fro m a theoretical perspective, and obtains a series of results r egarding assignments that provide the best and the worst availabilit y 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 re- sults demonstrate that even quite simple versions of the assignment problem can have surprising answers.