Epidemic Algorithms for Replicated Database Maintenance
📜 Abstract
When a database is replicated at many sites, maintaining mutual consistency among the sites in the face of updates is a significant problem. This paper describes several randomized algorithms for distributing updates and driving the replicas toward consistency. The algorithms are very simple and require few guarantees from the underlying communication system, yet they ensure that the effect of every update is eventually reflected in all replicas. The cost and performance of the algorithms are tuned by choosing appropriate distributions in the randomization step. The algorithms are closely analogous to epidemics, and the epidemiology literature aids in understanding their behavior. One of the algorithms has been implemented in the Clearinghouse servers of the Xerox Corporate Internet, solving long-standing problems of high traffic and database inconsistency.
✨ Summary
The paper established a foundational framework for applying epidemic or gossip-style communication to replicated database maintenance. It compared direct mail, anti-entropy, and rumor mongering, analyzing their trade-offs in propagation delay, network traffic, reliability, and residual inconsistency. It also introduced practical mechanisms for handling deletions, including timestamped death certificates and dormant death certificates, and showed how topology-aware partner selection could reduce traffic on critical network links. The Xerox Clearinghouse implementation provided an early industry deployment and reported reductions of more than four times in average link traffic and more than thirty times on certain critical links relative to uniform partner selection.
The work was subsequently extended in research on transaction-oriented epidemic replication. For example, a 2003 IEEE Transactions on Knowledge and Data Engineering paper explicitly develops epidemic algorithms for replicated databases using causally delivered transaction log records, including pessimistic, optimistic, and quorum-based variants. (researchgate.net) The original work also became a commonly cited foundation for later gossip-protocol research; the ACM record identifies the 1987 PODC publication and reports substantial subsequent citation. (doi.org) Industry discussions have connected the Xerox epidemic approach to modern gossip-based group-membership and failure-detection systems such as SWIM, although that connection is described retrospectively rather than as a direct implementation lineage in the paper itself. (hashicorp.com)