\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_1$, ..., $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_0$ of a complete 
binary tree of $n-1$ sites, with the distance from $s$ to $u_0$ 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.