Inconsistency Discovery

Discovery of inconsistencies is not a difficult problem - however unlike the mechanisms used in RMP [#!rmp!#] and SRM [#!van:95!#] inconsistencies due to simple packet loss cannot be discovered simply from the absence of a packet as we wish most such changes to be repaired by redundancy, and therefore do not need to see every packet at a receiver.

Instead we use a mechanism that ensures inconsistencies are resolved, irrespective of the number of packets lost. There are three parts to this inconsistency discovery scheme.

• Two schemes are based on the session messages each instance of the application sends periodically to indicate conference membership. These session messages are sent by each site with a rate that is dependent on the total number of sites in the conference. Thus the total session message rate is constant (albeit a low one). To detect inconsistencies, each session message carries two extra pieces of information - the timestamp of the most recent modification seen, and a checksum of all the data. If the timestamp given by another site is later than the latest change a receiver has seen, the receiver can request all changes from the missing interval without knowing what that data actually was. This is most useful when changes have happened during a network partition but all sites were passive when the partition was resolved. However, if a network partition was a resolved as a site was transmitting, the receiver may have the must recent changes, but not some older ones - hence the checksum is a last resort to discover that a problem has occurred, if not which data is missing.

• The third scheme is a more active scheme designed to prevent the above schemes from needing to be used where possible. We have a concept of the current site - this an instance of the application at the site which has most recently been active. If more than one site is active, any of those sites can be chosen as current site. The current site periodically multicasts out a summary packet giving the timestamps and IDs of all the most recently changed objects (lines and blocks). If a receiver has a different version (either older or newer) of one of these objects then it is entitled to either request the newer version from the current site, or to send its later version. The current site may change each time a new user modifies the document; however the rate that these summary packets are sent is a constant whilst any users are modifying the document - a new current site simply takes over from the previous one. In fact sometimes more than one site may think it is the current site at any one time.

An alternative to sending explicit summary packets might be for session and data packets to have an additional object ID and its modification timestamp added to them, and for all sites to take turns to report the state of the most recently modified objects. Indeed, depending on the choice of retransmission scheme, this may be preferable, but we have chosen not to use this scheme. We shall discuss why not after we have discussed the choice of retransmission scheme.