Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation

John R. Douceur and Roger P. Wattenhofer

Abstract

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 placement. Based on large-scale measurements, we assume that the distribution of machine availabilities 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.

Details

Publication typeInproceedings
Published inProceedings of 9th Annual European Symposium on Algorithms (ESA)
PublisherSpringer-Verlag
> Publications > Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation