Title :
A randomized technique for remote file comparison
Author :
Barbara, Daniel ; Lipton, Richard J.
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
A technique for file comparison is presented that is based in a set of signatures that are selected by a randomized algorithm. The sites performing the comparison agree on this randomized set of signatures before any comparison takes place. This technique proves to be very competitive with previously published algorithms. It has an advantage over previous techniques in that one can set up the algorithm to diagnose up to a given number of different pages. This is done by changing the total number of bits sent to guarantee that the expected number of falsely diagnosed pages remains under a given level. A metric for comparing the complexity of file comparison techniques is introduced, based on the number of bits that the algorithm needs to send in order to diagnose a given number of differing pages while keeping the probability of false diagnosis under a certain level of confidence
Keywords :
computational complexity; distributed processing; bits sent; complexity; confidence level; expected number; falsely diagnosed pages; metric; probability of false diagnosis; randomized algorithm; randomized technique; remote file comparison; set of signatures; sites; Application software; Binary trees; Computer networks; Computer science; Hardware; Humans; Plasma welding; Protocols;
Conference_Titel :
Distributed Computing Systems, 1989., 9th International Conference on
Conference_Location :
Newport Beach, CA
Print_ISBN :
0-8186-1953-8
DOI :
10.1109/ICDCS.1989.37925
