Dealing with Tentative Data Values in Disconnected Work Groups

Computer Science Laboratory
Xerox Palo Alto Research Center
Palo Alto, California 94304 U.S.A.

contact: theimer@parc.xerox.com

Now consider the case of a disconnected work group, that is, a group of collaborating individuals whose computers can reach each other but cannot communicate with relevant parts of the rest of the world. In order for such a group to get work done while "disconnected", it is necessary that members of the group be able to update data values and share the updated values within the group. However, these updates must be considered tentative since they may conflict with updates being performed concurrently outside the group.

Furthermore, tentative data does not necessarily remain local to a disconnected work group. Membership in the group may change over time, as members of the group leave it and new members join. Membership may also change because of a changing communications environment: network partitions may split the group in half as well as enable new members to join in who couldn't previously. The result is that people may belong to several disconnected work groups over time and the tentative data they manipulate may be seen by and affect the behavior of multiple groups. For example, a meeting tentatively scheduled in one disconnected work group might end up affecting the scheduling decisions of other disconnected work groups later on that include members from the first group.

The response to a detected conflict becomes much more complicated when the conflicting updates may have been seen by many users. There is no guarantee that all users who have seen a tentative update will be available when a conflict is detected, or that all new tentative data that depends on the conflict will be available. The challenge then is to find all current or previous members of the work group who have seen and acted on a conflicting update, arrange for them to be notified of the conflict, and assume that they can remember (and arrange to compensate for) whatever actions they took that depended on the conflicting data value.

As mentioned earlier, the problem is exacerbated by the fact that disconnected work group members will interact with other people in the system, who must also be notified of the conflict. Consequently, the number of people whose actions might depend on the value of a conflicting update grows over time, and the longer the state of an update must remain tentative, the more workwill likely be needed to undo its effects.

Finally, work groups can "splinter" and later have some or all fragments merge, at which point it becomes necessary to reconcile conflicts visible within the new group. Such conflict resolutions are themselves tentative, since they are based on tentative update values, and users of the resulting data values must be careful to remember this fact. If many of these dependencies and dependencies-of-dependencies are being kept in the heads of human beings, each new permutation of a disconnected work group's membership will cause added confusion. Figure 1 illustrates an example of this problem.

Trying to schedule a project meeting. Marvin forgets that the reconciliation deciding to hold the meeting on 12/14 is only tentative.

First, consider a document formatting system in which bibliographic references in documents are made by means of unique key strings that refer to a specific bibliographic entry in a shared bibliographic database. If someone adds a new bibliographic entry to the shared database while he is disconnected, he risks choosing a "unique" key string that will also get chosen by someone else adding a different bibliographic entry. Consequently, when bibliography database update conflicts occur, it is necessary to notify everyone who might have a document that contains a reference to the conflicting bibliographic entry; otherwise some documents risk using the wrong entry when they get reformatted.

In a single disconnected user scenario it is likely that a user's changes to a bibliographic database will get propagated to the rest of the system at the same time as the user's use of those changes in one or more document files. Consequently, the user is likely to remember that he must adjust his document files accordingly. In a disconnected work group scenario, various users might update and use the copy of a bibliographic database that resides on a single user's computer, while keeping their document files on their own computers. If the group then splits up, it will be the responsibility of the lone user who was keeping the copy of the bibliographic database to notify the others about any update conflicts that might invalidate the references in their document files.

Shared calendars are another difficult-to-handle example. A shared calendar system could be structured as a shared database representing meeting rooms, together with a private database for each user containing the meetings he or she was scheduled to attend. A conflict would arise in the shared data base if two disconnected groups tried to schedule meetings in the same room at the same time; in that case, one of the conflicting meetings would be cancelled or rescheduled, and the system should find and notify all the affected users. These, in turn, must update their private calendars accordingly. Furthermore, if any of the affected users has performed other derived actions---such as booking travel plans based on the assumption that a scheduled meeting would occur---then those users will have to remember to effect alternate travel bookings.

The consequence we take from this problem is that systems providing weakly-consistent, replicated data semantics should be structured so that all the relevant interactions among collaborating individuals and all the dependencies among data and actions be made explicit. Only then can update conflict resolution systems hope to maintain system integrity without having to depend entirely on the availability and reliability of human beings.