\boldhead{3.2 Spatial Distributions and Rumors}
Because anti-entropy effectively examines the entire database on each exchange, it is very robust. For example, consider a spatial distribution such that for every pair ($s$, $s^\prime$) of sites there is a nonzero probability that $s$ will choose to exchange data with $s^\prime$. 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.
Rumor mongering has a parameter that can be adjusted: as the spatial distribution is made less uniform, we can increase the value of $k$ in the rumor mongering algorithm to compensate. For {\it push-pull} rumor mongering on the CIN topology, this technique is quite effective. We have simulated the (Feedback, Counter, {\it push-pull}, No Connection Limit) variation of rumor mongering described in Section 1.4, using increasingly nonuniform spatial distributions. We found that once $k$ was adjusted to give 100\% distribution in each of 200 trials, that the traffic and convergence times were nearly identical to the results in Table 4. That is, there is a small finite $k$ that achieves the same results as $k = \infty$.
The fact that rumor mongering achieves the same results as Table 4 is a stronger fact than it might seem at first. The convergence times in Table 4 are given in cycles; however, the cost of an anti-entropy cycle is a function of the database size, while the cost of a rumor mongering cycle is a function of the number of active rumors in the system. Similarly, the compare traffic figures in Table 4 have different meanings when interpreted as pertaining to anti-entropy or rumor mongering. In general rumor mongering comparisons should be cheaper than anti-entropy comparisons, since they need to examine only the list of hot rumors.
We conclude that a nonuniform spatial distribution can produce a worthwhile improvement in the performance of {\it push-pull} rumor mongering, particularly the traffic on critical network links.
The {\it push} and {\it pull} variants of rumor mongering appear to be much more sensitive than {\it push-pull} to the combination of nonuniform spatial distribution and arbitrary network topology. Using (Feedback, Counter, {\it push}, No Connection Limit) rumor mongering and the spatial distribution (3.1.1) with $a$ = 1.2, the value of $k$ required to achieve 100\% distribution in each of 200 simulation trials was 36; convergence times were correspondingly high. Simulations for larger $a$ values did not complete overnight, so the attempt was abandoned.
We do not yet fully understand this behavior, but two simple examples illustrate the kind of problem that can arise. Both examples rely on having isolated sites, fairly distant from the rest of the network.
\vskip 15pt
\centerline{\bf Figure 1 \hskip 1.4in \bf Figure 2}
\penalty1000\vbox to 1.8in{\vfil\hbox to\hsize{\tentt <==<Figures.ip<\hfil}}
First, consider a network like the one shown in Figure 1, in which two sites $s$ and $t$ are near each other and slightly farther away from sites $u𡤁$, ..., $u←m$, which are all equidistant from $s$ and equidistant from $t$. (It is easy to construct such a network, since we are not required to have a database site at every network node). Suppose $s$ and $t$ use a $Q←s (d)^{-2}$ distribution to select partners. If $m$ is larger than $k$ there is a significant probability that $s$ and $t$ will select each other as partners on $k$ consecutive cycles. If {\it push} rumor mongering is being used and an update has been introduced at $s$ or $t$, this results in a catastrophic failure -- the update is delivered to $s$ and $t$; after $k$ cycles it ceases to be a hot rumor without being delivered to any other site. If {\it pull} is being used and the update is introduced in the main part of the network, there is a significant chance that each time $s$ or $t$ contacts a site $u←i$, that site either does not yet know the update or has known it so long that it is no longer a hot rumor; the result is that neither $s$ nor $t$ ever learns of the update.
As a second example, consider a network like the one shown in Figure 2. Site $s$ is connected to the root $u𡤀$ of a complete binary tree of $n-1$ sites, with the distance from $s$ to $u𡤀$ greater than the height of the tree. As above, suppose all sites use a $Q←s (d)^{-2}$ distribution to select rumor mongering partners. If $n$ is large relative to $k$, there is a significant probability that in $k$ consecutive cycles no site in the tree will attempt to contact $s$. Using {\it push} rumor mongering, if an update has been introduced at some node of the tree, the update may fail to be delivered to $s$ until it has ceased to be a hot rumor anywhere.
More study will be needed before the relation between spatial distribution and irregular network topology is fully understood. The examples and simulation results above emphasize the need to back up rumor mongering with anti-entropy to guarantee complete coverage. Given such a guarantee, however, {\it push-pull} rumor mongering with a spatial distribution appears quite attractive for the CIN.