Often, a computing device maintains data on a database, a list, a table, or a storage system. Such data can include state information relating to a set of variables that can correspond to operating system information, transmission information, and the like. The computing device can maintain local state information related to variable values associated with the particular computing device as well as state information regarding variable values for a number of additional connected computing devices. Because each computing device's state information may change, the modified state information is replicated from one computing device to the next through a network. Replication is a mechanism in which information held on a computing device is copied to one or more connected computing devices, all of which provide access to the same set of data. The term “replication” usually implies how to copy the entire source data collection or parts of it which have changed since the last replication.
In one form of replication, each computing device could continuously transmit its state information to every other computing device. In a special form of replication, often referred to as gossiping, state information about other connected computing devices maintained on a local computing device is exchanged from one computing device to another. As the process is repeated, a network of computing devices can update state information.
In order to facilitate the replication of information between two networked computing devices, reconciliation schemes are frequently implemented. Early reconciliation schemes involved merge operations between the information maintained on each host computing device. In its most basic form, a first host computing device would send all its data to a second host computing device. The second host computing device would simultaneously send all its data to the first host computing device. Consequently, each host updated its data based on the received information if the data was newer. Eventually, after sending and updating data between each host computing device, information would be resolved among all the host computing devices connected to the network. Early reconciliation schemes suffered from inefficiency. Under high update load and limited available network bandwidth, the amount of updated data introduced into the network would cause backlogs if significant. Consequently, backlogs caused message losses to occur for each host computing device and resulted in host computing devices having outdated information.
Compounding the backlogs and message losses due to reconciling host computing device information, each host computing device tried to transmit as much as information as it could to the other hosts. Because transmission information was stored locally on each host, host computing devices had no way of sharing bandwidth fairly.