This paper presents randomized algorithms for maintaining consistency in replicated databases. The authors describe three main approaches: direct mail, anti-entropy, and rumor mongering. Direct mail is timely but unreliable. Anti-entropy is reliable but slow. Rumor mongering is efficient but may not reach all sites. All three methods are analogous to epidemic processes, with rumor mongering being a complex epidemic. The authors analyze these methods and show that rumor mongering can be more efficient than anti-entropy. They also describe how to handle deletions in replicated databases using death certificates, which are spread like ordinary data. The authors also discuss spatial distributions for reducing network traffic, showing that a distribution proportional to $ d^{-2} $ is optimal for spreading updates on a line. The paper concludes that these algorithms can be used to maintain consistency in large, heterogeneous networks with high traffic and replication.This paper presents randomized algorithms for maintaining consistency in replicated databases. The authors describe three main approaches: direct mail, anti-entropy, and rumor mongering. Direct mail is timely but unreliable. Anti-entropy is reliable but slow. Rumor mongering is efficient but may not reach all sites. All three methods are analogous to epidemic processes, with rumor mongering being a complex epidemic. The authors analyze these methods and show that rumor mongering can be more efficient than anti-entropy. They also describe how to handle deletions in replicated databases using death certificates, which are spread like ordinary data. The authors also discuss spatial distributions for reducing network traffic, showing that a distribution proportional to $ d^{-2} $ is optimal for spreading updates on a line. The paper concludes that these algorithms can be used to maintain consistency in large, heterogeneous networks with high traffic and replication.