\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.