Efficient knowledge representation in data synchronization systems

• US 7,620,659 B2
• Filed: 02/09/2007
• Issued: 11/17/2009
• Est. Priority Date: 02/09/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kelley, Sean Michael, Novik, Lev, Khosravy, Moe, Pfenning, Jorg-Thomas, Clark, Michael Ray, Beckerman, Michael Scott
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): Le; Hung D
• Application Number:
  US11/673,415
• Publication Number:
  US 20080195759A1
• Time in Patent Office: 1,012 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A variety of flexible conflict resolution policies are provided for loosely coupled devices to implement according to a variety of different synchronization scenarios. Choosing a conflict resolution policy, such as “Most Frequent Updater,” “Priority,” “PerCent Change,” “Arbiter Deadlock Resolution,” etc., enables devices to select how and when to resolve such synchronization conflicts. In addition, with reference to a conflict log, a user or synchronizing application can roll back synchronization state to a time before a conflict may have arisen, so that the user or application can undo a resolution of a conflict and/or the user or application can apply an alternative conflict resolution policy moving forward from that time.

Claims

1. A method for synchronizing a set of objects between a first node and a second node of a plurality of nodes connectable via one or more networks, comprising:

employing a processor to execute computer executable instructions stored on a computer readable medium to perform the following acts;

initiating synchronization of the set of objects between the first node and the second node;

comparing knowledge of the second node concerning the set of objects with knowledge of the first node concerning the set of objects including determining that a conflict exists with respect to respective versions of at least one object of the set of objects maintained by the first and second node;

resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to at least one conflict resolution policy configurable by the first, or second node from a set of conflict resolution policies;

wherein said resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to a conflict resolution policy that favors the version originating from the node that has performed the most updates since the last synchronization;

enabling each node to communicate with a database of directives and independently executing the directives wherein the directives include at least one conflict resolution policy.

2. The method of claim 1, wherein said determining includes detecting from the knowledge of the second node and the first node whether an object of the set of objects independently evolved on the first node and second node.

3. The method of claim 1, wherein said resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to a conflict resolution policy that favors the version originating from the node having the highest priority.

4. The method of claim 1, wherein resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to a conflict resolution policy that favors the version originating from the node that has made the highest percentage of changes to the at least one object.

5. The method of claim 1, wherein said resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to an arbiter that determines the version to propagate on behalf of the first and second node.

6. The method of claim 1, wherein said resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to a conflict resolution policy that favors the version originating from the node that participates in the higher number of synchronization relationships with the plurality of nodes.

7. The method of claim 1, wherein said resolving includes resolving the conflict by selecting one of the versions to propagate to the plurality of nodes with reference to a conflict resolution policy that favors the version originating from the node that is closest to all other nodes as measured across all synchronization relationships of the plurality of nodes.

8. The method of claim 1, further comprising:

initiating synchronization by the first node or the second node with a third node;

comparing knowledge of the third node with knowledge of the first node or second node, respectively, concerning the set of objects including determining that a second conflict exists with respect to respective versions of at least one object of the set of objects maintained by the third node and the first or second node; and

resolving the second conflict by selecting one of the versions to propagate to the plurality of nodes with reference to at least one conflict resolution policy selected by the third node, or the first node or second node from a plurality of conflict resolution policies.

9. A first node of a plurality of nodes connectable via one or more networks that synchronizes a set of objects between the first node and any second node of the plurality of nodes, comprising:

a synchronization component that synchronizes the set of objects between the first node˜

any second node of the plurality of nodes, and detects whether at least conflict exists with respect to respective versions of at least one object of the set of objects maintained by the first and any second node;

a conflict log store that stores information representative of the at least one conflict;

a synchronization conflict resolution component that enables and executes the resolution of the at least one conflict by selecting one of the versions to propagate to the second node with reference to at least one conflict resolution policy selected by the first node from a plurality of conflict resolution policies; and

wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node that has made the highest percentage of changes to the at least one object;

a synchronization time control component allows an application or user of the first node to restore the at least one object to a time before the detection of the at least one conflict.

10. The first node of claim 9, wherein the synchronization time control component allows the application or user to restore the set of objects of the first node to a designated point in time, thereby rolling back any conflict resolution performed on the set of objects by the synchronization conflict resolution component after the designated point in time.

11. The first node of claim 10, wherein the synchronization time control component allows the application or user to apply a different at least one conflict resolution policy of the plurality of conflict resolution policies at the designated point in time, resolving any conflicts from the designated point in time with reference to the different at least one conflict resolution policy.

12. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node that has performed the most updates since the last synchronization.

13. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node having the highest priority.

14. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to an arbiter that determines the version to propagate on behalf of the first and second node.

15. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node that participates in the higher number of synchronization relationships with the plurality of nodes.

16. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node that is closest to all other nodes as measured across all synchronization relationships of the plurality of nodes.

17. The first node of claim 9, wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that minimizes a measurement of network traffic across all the plurality of nodes.

18. A first node of a plurality of nodes connectable via one or more networks that synchronizes a set of objects between the first node and any second node of the plurality of nodes, comprising:

a synchronization component that synchronizes the set of objects between the first node any second node of the plurality of nodes by comparing knowledge of the second node concerning the set of objects with knowledge of the first node concerning the set of objects, wherein the synchronization component determines whether at least conflict exists with respect to respective versions of at least one object of the set of objects maintained by the first and any second node, and the resolution of any least conflict through communication with a database of at least one conflict resolution policy; and

wherein said synchronization conflict resolution component resolves the at least one conflict by selecting one of the versions to propagate to the second node with reference to a conflict resolution policy that favors the version originating from the node that has made the highest percentage of changes to the at least one object;

a conflict log store that stores information representative of the at least one conflict so that the first node can defer resolving the at least one conflict as between the first and any second node at a later time.