\boldhead{1.5 Backing Up a Complex Epidemic with Anti-entropy}

We have seen that a complex epidemic algorithm can spread updates rapidly with very low network traffic. Unfortunately, a complex epidemic can fail; that is, there is a nonzero probability that the number of infective sites will fall to zero while some sites remain susceptible. This event can be made extremely unlikely; nevertheless, if it occurs, the system will be in a stable state in which an update is known by some, but not all, sites. To eliminate this possibility, anti-entropy can be run infrequently to back up a complex epidemic, just as it is used in the Clearinghouse to back up direct mail. This ensures with probability 1 that every update eventually reaches (or is superseded at) every site.

When anti-entropy is used as a backup mechanism, there is a significant advantage in using a complex epidemic such as rumor mongering rather than direct mail for initial distribution of updates. Consider what should be done if a missing update is discovered when two sites perform anti-entropy. A conservative response would be to do nothing (except make the databases of the two sites consistent, of course), relying on anti-entropy eventually to deliver the update to all sites. A more aggressive response would be to redistribute the update, using whatever mechanism is used for the initial distribution; e.g., mail it to all other sites or make it a hot rumor again. The conservative approach is adequate in the usual case that the update is known at all but a few sites. However, to deal with the occasional complete failure of the initial distribution, a redistribution step is desirable.

Unfortunately, the cost of redistribution by direct mail can be very high. The worst case occurs when the initial distribution manages to deliver an update to approximately half the sites, so that on the next anti-entropy cycle each of O($n$) sites attempts to redistribute the update by mailing it to all $n$ sites, generating O($n^2$) mail messages. The Clearinghouse originally implemented redistribution, but we were forced to eliminate it because of its high cost.

Using rumor mongering instead of direct mail would greatly reduce the expected cost of redistribution. Rumor mongering is ideal for the simple case in which only a few sites fail to receive an update, since a single hot rumor that is already known at nearly all sites dies out quickly without generating much network traffic. It also behaves well in the worst-case situation mentioned above: if an update is distributed to approximately half the sites, then O($n$) copies of the update will be introduced as hot rumors in the next round of anti-entropy. This actually generates less network traffic than introducing the rumor at a single site.

This brings us to an interesting way of combining rumor mongering and anti-entropy. Recall that we described earlier a variation of anti-entropy called {\it peel back} that required an additional index of the database in timestamp order. The idea was to have sites exchange updates in reverse timestamp order until they reached checksum agreement on their entire databases. {\it Peel back} and rumor mongering can be combined by keeping the updates in a doubly-linked list rather than a search tree. Whereas before we needed a search tree to maintain reverse timestamp order, we now use a doubly-linked list to maintain a local activity order: sites send updates according to their local list order, and they receive the usual rumor feedback that tells them when an update was useful. The useful updates are moved to the front of their respective lists, while the useless updates slip gradually deeper in the lists. This combined variation is better than {\it peel back} alone because: 1) it avoids the extra index, and 2) it behaves well when a network partitions and rejoins. It is better than rumor mongering alone because it has no failure probability. In practice one would probably not send one update at a time, but batch together a collection of updates from the head of the list. This set is analogous to the hot rumor list of rumor mongering, but membership is no longer a binary matter since if the first batch fails to reach checksum agreement, then more batches are sent. If necessary, any update in the database can become a hot rumor again.