Title :
A class of randomized strategies for low-cost comparison of file copies
Author :
Barbará, Daniel ; Lipton, Richard J.
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
fDate :
4/1/1991 12:00:00 AM
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 4flog(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 frf, where r can be made to approach 1, are also presented. A comparison of these techniques is discussed
Keywords :
algorithm theory; file organisation; security of data; differing pages; file copies; randomized signatures; randomized strategies; remotely located file copies; Broadcasting; Costs; Database systems; Distributed algorithms; Fault tolerance; Hardware; Humans; Sun; Transaction databases; Voting;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on