\boldhead{4. Conclusions}

It is possible to replace complex deterministic algorithms for replicated database consistency with simple randomized algorithms that require few guarantees from the underlying communication system. The randomized anti-entropy algorithm has been implemented on the Xerox Corporate Internet providing impressive performance improvements both in achieving consistency and reducing network overhead traffic. By using a well chosen spatial distribution for selecting anti-entropy partners, the implemented algorithm reduces average link traffic by a factor of more than 4 and traffic on certain critical links by a factor of 30 when compared with an algorithm using uniform selection of partners.

The observation that anti-entropy behaves like a simple epidemic led us to consider other epidemic-like algorithms such as rumor mongering, which shows promise as an efficient replacement for the initial mailing step for distributing updates. A backup anti-entropy scheme easily spreads the updates to the few sites that do not receive them as a rumor. In fact, it is possible to combine a {\it peel back} version of anti-entropy with rumor mongering, so that rumor mongering never fails to spread an update completely.

Neither the epidemic algorithms nor the direct mail algorithms can correctly spread the absence of an item without assistance from death certificates. There is a trade-off between the retention time for death certificates, the storage space consumed, and the likelihood of old data undesirably reappearing in the database. By retaining dormant death certificates at a few sites we can significantly improve the network's immunity to obsolete data at a reasonable storage cost.

There are more issues to be explored. Pathological network topologies present performance problems. One solution would be to find algorithms that work well with all topologies; failing this, one would like to characterize the pathological topologies. Work still needs to be done on the analysis and design of epidemics. So far we have avoided differentiating among the servers; better performance might be achieved by constructing a dynamic hierarchy, in which sites at high levels contact other high level servers at long distances and lower level servers at short distances. (The key problem with such a mechanism is maintaining the hierarchical structure.)

\boldhead{5. Acknowledgments}

We would like to thank Mike Paterson for his help with parts of the analysis, and Subhana Menis and Laurel Morgan for threading the arcane production maze required to produce the camera ready copy of this paper.