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 is an early systematic treatment of epidemic, or gossip-style, algorithms for maintaining eventual consistency among widely replicated databases. It compares direct mail, anti-entropy, and rumor mongering using propagation delay, network traffic, and residual inconsistency as key metrics. Its main design recommendations are to use randomized pairwise exchanges, favor pull or push-pull over push when repairing sparse inconsistencies, use checksums or timestamp-oriented exchange to reduce the cost of full database comparison, and combine fast but probabilistic rumor spreading with periodic anti-entropy when complete coverage is required.
The paper also addresses deletion through timestamped death certificates and proposes dormant certificates to reduce storage costs while limiting the resurrection of obsolete data. Its topology-aware partner-selection experiments showed that nonuniform distributions could substantially reduce traffic on critical links; the resulting anti-entropy method was deployed in Xerox’s Clearinghouse service.
Later distributed-systems research adopted closely related mechanisms. The SWIM membership protocol explicitly cites this paper and uses infection-style dissemination to spread membership updates with slowly growing, approximately logarithmic dissemination latency. (cs.cornell.edu) Amazon’s Dynamo subsequently implemented anti-entropy replica synchronization using Merkle trees and used randomized gossip to propagate membership changes, illustrating the continued industry relevance of the paper’s replica-repair and epidemic-dissemination patterns. (cdn.amazon.science) A later survey-style research work on non-uniform replication also lists the paper alongside Dynamo and Cassandra as part of the development of replicated-storage techniques. (drops.dagstuhl.de)