A class of randomized strategies for low-cost comparison of file copies
- 1 April 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 2 (2) , 160-170
- https://doi.org/10.1109/71.89062
Abstract
A class of algorithms that use randomized signatures to compare remotely located file copies is presented. A simple technique that sends on the order of 4/sup f/log(n) bits, where f is the number of differing pages that are to be diagnosed and n is the number of pages in the file, is described. A method to improve the bound in the number of bits sent, making them grow with f as flog(f) and with n as log(n)log(log(n)), and a class of algorithms in which the number of signatures grows with f as fr/sup f/, where r can be made to approach 1, are also presented. A comparison of these techniques is discussed.<>Keywords
This publication has 3 references indexed in Scilit:
- Exploiting symmetries for low-cost comparison of file copiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A Parity Structure for Large Remotely Located Replicated Data FilesIEEE Transactions on Computers, 1983
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952