Algorithms That Can Be Wrong, but with Diminishing Probability
In this section we study algorithms that may be wrong, but with diminishing probability. With a modest computation, we can assure that the likelihood of producing a wrong answer can be made arbitrarily small.
Testing Inequality of Databases
Suppose a company keeps multiple distributed copies of a very large database to permit efficient queries from many sites. Queries of the database are much more frequent than updates, and updates are applied at every copy. Also, an adversary with access to the updates may change them. One approach to assuring coherence of the multiple copies in spite of potential adversaries is to send a copy of the database from any site to every other site and test for inequality. But the size of the database makes this transmission prohibitively expensive.
Another approach is to transmit a fingerprint of any copy to every other site and then test whether the fingerprint at every other site is equal to the transmitted fingerprint. More explicitly, we consider a database to be a (large) sequence of bits (b0, ... bn−1). The fingerprint of (b0 ... bn−1) is (b0 + b1*21 + b222 + ... ... bnn-1*2n−1) mod p for some randomly chosen prime number p. We only need to transmit on the order of log (p) bits. If the transmitted fingerprint is different than the fingerprint of the local database, then one can say with certainty that the databases are different. If the fingerprints are the same, however, one can't ...
Get Algorithms in a Nutshell now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
