1 Introduction
Data replication is an optimization technique well known in the distributed systems and database communities as a means of achieving better access times to data (data locality) and/or fault tolerance (data availability) [Bres99], [Karg99], [Tewa99]. This technique appears clearly applicable to data distribution problems in large-scale scientific collaborations, due to their globally distributed user communities and distributed data sites. As an example of such an environment, we consider the High Energy Physics community where several thousand physicists want to access the Terabytes and even Petabytes of data that will be produced by large particle detectors around 2006 at CERN, the European Organization for Nuclear Research.