在这个小节中，我们要学习的是这样一种算法：它的结果可能是错的，但是会衰减错误率。通过适度的计算，它的错误率可以非常低。
检测数据库间的不一致
假设某个公司为了快速响应来自许多不同点的查询需求而为一个大型数据库创建了多个复本，数据库的查询请求远多于更新，更新操作会作用到每个复本上。另外，还会有其他的更新会修改数据库。确保所有复本一致的一个方法是将任意某个点的数据库复本发送给所有其他点以检测一致性。不过这个数据库规模之大会让传送复本的代价无比之高。
另外一个方法就是将其中任意一份复本的特征值发送到其他点上，检测这些点上复本的特征值是否与此吻合。更明确的说法是，假设数据库是一个超长的比特串（b0……bn-1），这个长串的特征值为(b0+b1×21+b2×22+……+bn-1×2n-1)mod p，p是随机选择的一个素数，我们所要发送的只是一个长度为log(p)的比特串。如果发送的特征值与当前数据库的特征值不同，则可以肯定两个数据库之间不一致，不过特征值相同也不能确定两个数据库完全一致。而不同数据库具有相同特征值的概率为1/p。要降低错误率重复测试多次就可以了。例10-3给出了该一致性检测算法的伪码。
例10-3：一致性检测算法的伪码