This work originated in our study of the Clearinghouse servers [Op] on the Xerox Corporate Internet (CIN). The worldwide CIN comprises several hundred Ethernets connected by gateways (on the CIN these are called {\it internetwork routers}) and phone lines of many different capacities. Several thousand workstations, servers, and computing hosts are connected to CIN. A packet enroute from a machine in Japan to one in Europe may traverse as many as 14 gateways and 7 phone lines.

The Clearinghouse service maintains translations from three-level, hierarchical names to machine addresses, user identities, etc. The top two levels of the hierarchy partition the name space into a set of {\it domains}. Each domain may be stored (replicated) on as few as one, or as many as all, of the Clearinghouse servers, of which there are several hundred.

Several domains are in fact stored at all Clearinghouse servers in CIN. In early 1986, many of the network's observable performance problems could be traced to traffic created in trying to achieve consistency on these highly replicated domains. As the network size increased, updates to domains stored at even just a few servers propagated very slowly.

When we first approached the problem, the Clearinghouse servers were using both direct mail and anti-entropy. Anti-entropy was run on each domain, in theory, once per day (by each server) between midnight and 6 a.m. local time. In fact, servers often did not complete anti-entropy in the allowed time because of the load on the network.

Our first discovery was that anti-entropy had been followed by a remailing step: the correct database value was mailed to all sites when two anti-entropy participants had previously disagreed. More disagreement among the sites led to much more traffic. For a domain stored at 300 sites, 90,000 mail messages might be introduced each night. This was far beyond the capacity of the network, and resulted in breakdowns in all the network services: mail, file transfer, name lookup, etc.

Since the remailing step was clearly unworkable on a large network our first observation was that it had to be disabled. Further analysis showed that this would be insufficient: certain key links in the network would still be overloaded by anti-entropy traffic.

Our explorations of spatial distributions and rumor mongering arose from our attempt to further reduce the network load imposed by the Clearinghouse update process.