{\noindent \bf 3.2 Epidemic and Spatial Distributions}
Because anti-entropy examines the entire data base on each exchange, it is very robust. For example, consider a spatial distribution such that for every pair of sites there is a nonzero probability of each site choosing to exchange data with the other. It is easy to show that anti-entropy converges with probability 1 using such a distribution, since under those conditions every site eventually exchanges data directly with every other site.
Rumor mongering, on the other hand, runs to quiescence -- every rumor eventually becomes inactive, and if it has not spread to all sites by that time it will never do so. Thus it is not sufficient that the site holding a new update eventually contact every other site; the contact must occur "soon enough", or the update can fail to spread to all sites. This suggests that rumor mongering might be less robust than anti-entropy against changes in spatial distribution and network topology. In fact we have found this to be the case.
A simple example illustrates the kind of problem that can arise. Consider a pair of sites $s$ and $t$ at distance 0 (i.e. on the same local net), located at a "hub" of the internet, so the number of sites at distance 1 from them is comparatively large. Reasonable values for $Q$ might be $Q(0) = 2$, $Q(1) = 30$. Using the $1/Q(d)^2$ distribution, $s$ and $t$ are about 8 times more likely to choose each other than to choose outside their local net. Now suppose an update is performed at site $s$. Using the (Feedback, Counter, Push, No Connection Limit) variation of rumor mongering described in Section 1.4, with $k = 5$, there is better than a 25\% chance that $s$ and $t$ will simply pass the update back and forth between them until both their counters reach $k$, so the update {\sl never escapes from the local net at which it was created}. We have observed behavior like this in our simulations on the CIN topology.
Fortunately, both rumor mongering and the spatial distribution have parameters that can be adjusted: we can increase the value of $k$ in the rumor mongering, and we can adjust the distribution to make it more nearly uniform. Table 3 below gives simulation results for the (Feedback, Counter, Push, Connection Limit = 1, HuntLimit = 1) variation of rumor mongering using increasingly nonuniform spatial distributions, with $k$ values adjusted to give near 100\% distribution.
???TABLE OF SIMULATION RESULTS BELONGS HERE???
\noindent
Observations:
\item{1.} Unfortunately the traffic figures in Table 3 are not directly comparable to those in Table 2, since in general rumor mongering conversations should be much cheaper than anti-entropy conversations.
\item{2.} Similarly, convergence time figures in Table 3 cannot be compared directly to those in Table 2. Both figures are given in cycles; however, the cost of an anti-entropy cycle is a function of the data base size, while the cose of a rumor mongering cycle is a function of the number of active rumors in the system. Ignoring fixed overhead, the cost of rumor mongering depends on the rate at which new updates are injected into the system, but is independent of the rate at which rumor mongering cycles are performed.
\item{3.} As we make the distribution more nonuniform, the $k$ value required to ensure complete distribution increases. The total number of cycles before convergence also increases fairly rapidly.
\item{4.} As we make the distribution more nonuniform, The mean total traffic per link, decreases slightly; and the mean traffic on the critical transatlantic link decreases dramatically.
\noindent
Although the effect is not as dramatic as with anti-entropy, we conclude that a nonuniform spatial distribution can produce a worthwhile improve the performance of rumor mongering, particularly the traffic on critical network links.