Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation

We examine the replica placement aspect of a distributed peer-to-peer file system that replicates and stores files on ordinary desktop computers. It has been shown that some desktop machines are available for a greater fraction of time than others, and it is crucial not to place all replicas of any file on machines with low availability. In this paper we study the efficacy of three hill-climbing algorithms for file replica replacement. Based on large-scale measurements, we assume that the distribution of machine availabilities will be uniform. Among other results we show that the MinMax algorithm is competitive, and that for growing replication factor the MinMax and MinRand algorithms have the same asymptotic worst-case efficacy. To appear in the Proceedings of the 9th Annual European Symposium on Algorithms , Aarhus, Denmark, August 2001.