System and method for distributed conflict resolution between data objects replicated across a computer network

• US 5,787,262 A
• Filed: 06/26/1996
• Issued: 07/28/1998
• Est. Priority Date: 06/26/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Norin, Scott, Benson, Max Loell, Shakib, Darren Arthur
• Primary Examiner(s): Rinehart, Mark H.
• Application Number:
  US08/673,161
• Time in Patent Office: 762 Days
• Field of Search: 395/200.31, 395/200.34, 395/200.35, 395/200.47, 395/712, 395/182.04, 395/200.43, 395/200.44, 395/200.48, 395/200.59, 395/200.78 , 395/683, 395/726, 707/201, 707/203, 707/8, 707/10, 707/202, 370/390
• US Class Current: 709/205
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method for distributed conflict resolution between different versions of the same data object which are replicated across a computer network is disclosed. The invention can be utilized with and adapted to any desired replication process. The conflict resolution process allows identification and resolution of conflicts with little or no increased message traffic on the network. The conflict resolution process is independent of the order in which conflicts are resolved and all replica nodes in the enterprise will eventually resolve the conflict in exactly the same manner. The method is adapted for resolution of conflicts between data objects or between objects which define the properties of sets of data objects. The final selection of which version of the object should be maintained and which version of the object should be deleted can be fully automated, completely manual, or a combination of the two.

Claims

1. In a network comprising a plurality of nodes each of which can make changes to local copies of a replica object and each of which transmit any changes made to other nodes in the network, a method for each node (1) to independently detect conflicts that arise when two or more copies of the replica object are changed to introduce conflicts and (2) to take steps to resolve the conflicts without interrupting normal operation of the network the method comprising the steps of:

keeping at a local node a local copy of the replica object and a local change history comprising globally unique change numbers that together identify all changes that have been made to said local copy, whether at said local node or at other nodes in the network;

receiving, from another node in the network, at least one message comprising a received copy the replica object and a received change history;

detecting if a conflict exists between said received copy and said local copy and taking steps to resolve any detected conflict without interrupting normal operation of the network by performing at least the steps of;

comparing said received change history with said local change history and declaring a conflict only if one of either said received change history or said local change history does not contain all the changes of the other;

if a conflict is declared then creating a new copy of the replica object that can be changed and transmitted to other replica nodes without interrupting normal operation of the network by performing at least the steps of;

executing a predetermined sequence of steps that deterministically select one of either said received copy or said local copy as a winner copy; and

attaching the copy not selected as the winner copy to the winner copy; and

if a conflict is not declared, then replacing said local copy with said received copy if said received copy contains all changes of said local copy, otherwise discarding said received copy and retaining said local copy.

2. A method for discovering and resolving conflicts as recited in claim 1 wherein each node in the network has a unique ID and wherein the local copy of the replica object and the received copy of the replica object each have a time stamp and wherein the predefined sequence of steps comprises:

selecting, as the winner copy, the copy of the object with the later time stamp; and

selecting, as the winner copy, the copy of the object which was changed by the node with the largest unique ID, if the time stamps of the received copy of the replica object and the local copy of the replica object are the same.

3. A method for discovering and resolving conflicts as recited in claim 1 further comprising the step of attaching the winner copy to itself.

4. A method for discovering and resolving conflicts as recited in claim 1 wherein said change history comprises a list of globally unique IDs which identify the latest change made by nodes in the network which have changed the local copy of the replica object.

5. A method for discovering and resolving conflicts as recited in claim 1 further comprising the step of notifying one or more users of the conflict.

6. A method for discovering and resolving conflicts as recited in claim 1 wherein the replica object comprises a plurality of data set properties having at least one time stamp indicating the time that said plurality of data set properties were last modified.

7. A method for discovering and resolving conflicts as recited in claim 6 further comprising the step of selecting as the winner copy the copy of the replica object with the later time stamp so that the winner copy of the replica object has at least some of the data set properties of the replica object selected as the winner copy.

8. A method for discovering and resolving conflicts as recited in claim 7 further comprising the step of replacing data set properties of the winner copy having individual time stamps with data set properties of the copy not selected as the winner copy having individual time stamps which are later in time than the individual time stamps of the winner copy.

9. In a network comprising a plurality of nodes each of which can make changes to local copies of a replica object and each of which transmit any changes made to other nodes in the network, a method for each node (1) to independently detect conflicts that arise when two or more copies of the replica object are changed to introduce conflicts and (2) to take steps to resolve the conflicts without interrupting normal operation of the network the method comprising the steps of:

keeping at a local node a local copy of the replica object and a local change history comprising globally unique change numbers that together identify all changes that have been made to said local copy, whether at said local node or at other nodes in the network;

receiving, from another node in the network at least one message comprising a received copy of the replica object and a received change history;

comparing said received change history with said local change history and declaring a conflict if one of either said received change history or said local change history does not contain all the changes of the other;

performing a predetermined sequence of steps to select a winner copy of the replica object from among the received copy of the replica object and the local copy of the replica object and creating a conflict object by attaching to said winner copy at least the copy of the replica object not selected as the winner copy;

making a change to said conflict object; and

replicating said change to said conflict object to other nodes in the network.

10. A method for discovering and resolving conflicts as recited in claim 9 further comprising the step of replacing the local copy of the replica object with the received copy of the replica object if no conflict exists and if the received replica object contains changes not found in the local replica object.

11. A method for discovering and resolving conflicts as recited in claim 10 wherein the local change history comprises the latest change made by nodes in the network which have changed the replica object.

12. A method for discovering and resolving conflicts as recited in claim 11 wherein each copy of the replica object has a time stamp and wherein each node in the network has a unique ID and wherein the sequence of steps used to select the winner copy comprises:

selecting, as the winner copy, the copy of the object with the later time stamp; and

selecting, as the winner copy, the copy of the object which was changed by the node with the largest unique ID, if the time stamps of the received copy of the replica object and the local copy of the replica object are the same.

13. A method for discovering and resolving conflicts as recited in claim 12 further comprising the step of attaching the winner copy to itself.

14. A method for discovering and resolving conflicts as recited in claim 13 further comprising the step of initiating final resolution of the conflict.

15. In a network comprising a plurality of computer systems interconnected by networking means, each of said computer systems adapted to make changes to local copies of a replica object and transmit any changes made to other computer systems, an article of manufacture for use in a one of the computer systems comprising:

program storage means, accessible by a CPU of a local computer system, for storing and providing, to the CPU, program code means, said program code means comprising;

means for receiving from other computer systems, via the networking means, at least one message comprising a received copy of a replica object and a received change history identifying changes made to said replica object;

means for determining if a conflict exists between a local copy of the replica object and said received copy of the replica object;

means for selecting a winner copy of the replica object from among the local copy of the replica object and the received copy of the replica object; and

means for attaching to said winner copy at least the copy of the object not selected as the winner copy in order to create a conflict object that can be transferred between the computer systems just like other replica objects.

16. An article of manufacture as recited in claim 15 wherein the means for determining if a conflict exists comprises means for comparing the local copy of the replica object to the received copy of the replica object.

17. An article of manufacture as recited in claim 16 wherein the means for comparing the local copy of the replica object to the received copy of the replica object compares a change history of the local copy of the replica object to a change history of the received copy of the replica object.

18. An article of manufacture as recited in claim 15 wherein the program code means further comprises means for final conflict resolution.

19. An article of manufacture as recited in claim 18 wherein the means for final conflict resolution comprises means for notifying one or more owners of the replica object that a conflict exists.

20. An article of manufacture as recited in claim 18 wherein the means for final conflict resolution further comprises means for presenting to an owner of the replica object the conflicts that exist.

21. An article of manufacture as recited in claim 15 wherein local copy of the replica object and the received copy of the replica object each have an associated time stamp and wherein the means for selecting a winner copy of the replica object selects the object with the latest time stamp.

22. An article of manufacture as recited in claim 21 wherein each computer system in the network has a unique ID and wherein the means for selecting a winner copy of the replica object selects the copy of the replica object changed by the system with the largest unique ID if the time stamps of each copy of the replica object is the same.

23. An article of manufacture as recited in claim 15 wherein the means for attaching to the winner copy at least the copy of the replica object not selected as the winner copy comprises means for attaching the winner copy to itself.

24. An article of manufacture for use in any one of a plurality of computer system, each of which can make changes to local copies of a replica object and each of which transmit any changes made to other computer systems through networking means, said article of manufacture comprising:

program storage means, accessible by CPU of a local computer system, for storing and providing, to the CPU, program code means, said program code means comprising;

means for determining if a conflict exists between a local copy of a replica object and a received copy of a replica object, said local copy of the replica object and said received copy of the replica object comprising a plurality of data set properties and one or more time stamps associated with one or more data set properties;

means for creating a new copy of the replica object that can be changed and transmitted to other replica nodes without interrupting normal operation of the network comprising;

means for selecting a winner copy of the replica object from among the local copy of the replica object and the received copy of the replica object;

means for attaching to the winner copy of the replica object, the copy of the replica object not selected as the winner copy; and

means for placing in the winning copy of the replica object those properties from the local copy of the replica object and the received copy of the replica object having the latest associated time stamp.

25. An article of manufacture as recited in claim 24 wherein the program code means further comprises means for placing in the winning copy of the replica object those properties from the local copy of the replica object and the received copy of the replica objects which have no corresponding entry in either the local copy of the replica object or the received copy of the replica object.

26. An article of manufacture for use in any of a plurality of nodes each of which can make changes to local copies of a replica object and each of which transmit any changes made to other nodes in a manner so that each node is able (1) to independently detect conflicts that arise when two or more copies of the replica object are changed to introduce conflicts and (2) to take steps to resolve the conflicts without interrupting normal operation of the network, the article of manufacture comprising:

program storage means for storing and providing program code means, said program code means comprising;

means for keeping at a local node a local copy of the replica object and a local change history comprising globally unique change numbers that together identify all changes that have been made to said local copy, whether at said local node or at other nodes in the network;

means for receiving, from another node in the network, at least one message comprising a received copy of the replica object and a received change history;

means for detecting if a conflict exists between said received copy and said local copy and taking steps to resolve any detected conflict without interrupting normal operation of the network, said means for detecting comprising;

means for comparing said received change history with said local chance history;

means for declaring a conflict only if one of either said received change history or said local change history does not contain all the changes of the other;

means for resolving a declared conflict comprising (1) means for creating a new copy of the replica object that can be changed and transmitted to other replica nodes without interrupting normal operation of the network, said new copy comprising a winner copy the replica object and at least one attached copy of the replica object (2) means for executing a predetermined sequence of steps that deterministically select one of either said received copy or said local copy as said winner copy, and (3) means for attaching the copy not selected as the winner copy to the winner copy; and

means for replacing said local copy with said received copy if said received copy contains all changes of said local copy, otherwise discarding said received copy and retaining said local copy.