Methods and systems for halting synchronization loops in a distributed system

• US 7,730,167 B2
• Filed: 04/30/2004
• Issued: 06/01/2010
• Est. Priority Date: 04/30/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Starbuck, Bryan T.
• Primary Examiner(s): Bruckart; Benjamin R
• Assistant Examiner(s): Ali; Farhad
• Application Number:
  US10/835,980
• Publication Number:
  US 20050262310A1
• Time in Patent Office: 2,223 Days
• Field of Search: 709220-221, 709/206
• US Class Current: 709/221
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/275 Synchronous replication

Abstract

The present provides for consistent resolution of data conflicts when synchronizing data between two or more devices in order to reduce the likelihood of an infinite synchronization loop within a distributed computing system. More particularly, example embodiments provide for a conflict resolution algorithm capable of generating unique values for properties that are in conflict. Data selection criteria can then be used to determine which of the properties should be used to resolve the conflict. Such data selection criterion increases the likelihood of providing consistent resolution of similar data conflicts between other devices in the distributed system.

Claims

1. In a distributed computing system capable of synchronizing properties, a method of providing consistent resolution for synchronization conflicts in order to reduce infinite synchronization loops within the distributed system, the method comprising acts of:

at a local machine connectable to a plurality of remote devices;

receiving remote device data that includes a remote property needing to be synchronized with a local property, the remote device data having been input at a first remote device, wherein the first remote device is a low fidelity device that is unable to maintain time date information and the remote device data being low fidelity data;

accessing local machine data that includes the local property needing to be synchronized with the remote property;

after receiving the remote device data and accessing the local machine data, determining that a conflict exists between the remote property and the local property;

after determining that the conflict exists at the local machine, and in response to determining that the conflict exists;

utilizing a conflict resolution algorithm to generate a remote value from the remote property;

utilizing the conflict resolution algorithm to generate a local value from the local property;

applying data selection criteria to a comparison of the remote value to the local value, and in a manner that reduces infinite synchronization loops among the local machine and two or more remote devices having corresponding properties for synchronization, wherein applying data selection criteria comprises;

at a binary bit level, summing bits of the remote value generated from the remote property to generate a first sum;

at a binary bit level, summing bits of the local value generated from the local property to generate a second sum; and

determining which of the first and second sums has a greater value or a lesser value; and

based at least on which of the first sum and second sum has a greater value or a lesser value, selecting the first sum or the second sum, and applying either the remote property or the local property associated with the selected of the first sum or the second sum for synchronization with the local machine or remote device, respectively.

2. The method of claim 1, wherein the conflict resolution algorithm is transitive.

3. The method of claim 1, wherein the determined property to be used for synchronization is a default value, and a user interface is presented to a user that highlights the default value.

4. The method of claim 3, wherein multiple conflicts exists and multiple default values are generated utilizing the conflict resolution algorithm, and the user of the local machine is presented with an option within the user interface to apply all the multiple default values.

5. The method of claim 1, wherein the determined property to be used for synchronization is automatically chosen with no user input.

6. The method of claim 1, wherein the conflict resolution algorithm is a hash function and the data selection criteria bases selection between the remote value and the local value on which is the greatest or least value.

7. The method of claim 1, wherein the conflict resolution algorithm chooses at least a portion of the remote property and a corresponding portion of the local property, and the remote and local values are based on the addition of a number of positive or negative bits, and the data selection criteria is a choice of the greatest or least value between the remote value and the local value.

8. The method of claim 1, wherein the properties correspond to a contact and are one or more of an address, phone number, email address, or web page.

9. In a distributed computing system capable of synchronizing properties, a method of providing consistent resolution of synchronization and avoiding infinite synchronization loops within the distributed system, the method comprising:

at a local machine that is connectable to a plurality of remote devices and is in communication with at least one of the plurality of remote devices;

an act of receiving remote device data from the at least one of the plurality of remote devices, the remote data being low fidelity data in that the at least one of the plurality of remote devices is unable to maintain time date information, and the remote data including a remote property needing to be synchronized with a local property;

an act of accessing local machine data that includes the local property needing to be synchronized with the remote property;

an act of determining that a conflict exists between the remote property and the local property, wherein the remote device is a low-fidelity that does not keep time/date information for the remote property, the local machine does not maintain data for the remote and local property for syncing, or both, and wherein determining that a conflict exists after receiving the remote data and after accessing the local machine data; and

after determining that the conflict exists, and in response thereto, a step for appropriately selecting a default property value based on applying data selection criteria to a remote value generated from the remote property and a local value generated from the local property, wherein the remote value and local value are generated using a conflict resolution algorithm and applying at least a portion of the remote property and local property respectively thereto, wherein the data selection criteria of which portions of the remote and local properties to use comprises an evaluation of a binary bit representation for the remote value compared with the local value, and wherein application of the selection criteria for selecting the default property substantially avoids infinite synchronization loops among three or more devices having corresponding properties for synchronization, wherein evaluation of a binary bit representation for the remote value compared with the local value comprises;

at a binary bit level, summing bits of the remote value generated from the remote property to generate a first sum;

at a binary bit level, summing bits of the local value generated from the local property to generate a second sum;

determining which of the first sum and the second sum has a greater value or a lesser value; and

selecting either the remote property or the local property for synchronization with the local machine or remote device by selecting the first sum or the second sum, based on which has the greater or lesser value, and applying the property associated with the selected of the first sum or the second sum to both the local device and the remote device.

10. The method of claim 9, wherein the conflict resolution algorithm is transitive.

11. The method of claim 10, wherein multiple conflicts exists and multiple default values are generated utilizing the conflict resolution algorithm, and the user is presented with an option within the user interface to apply all the multiple default values.

12. The method of claim 10, wherein the conflict resolution algorithm is a hash function applied after previously determining that a conflict exists between the local property on the local machine and the remote property received from the at least one of the plurality of remote devices, and wherein the data selection criteria bases selection of the local or remote property on a greatest or least value between the remote value and the local value.

13. The method of claim 10, wherein the conflict resolution algorithm chooses at least a portion of the remote property and a corresponding portion of the local property, and the remote and local values are based on adding together a plurality of positive or negative bits, and the data selection criteria bases selection on the greatest or least value between the remote value and the local value.

14. The method of claim 9, wherein the selected default property valued is highlighted at a user interface and presented to a user.

15. The method of claim 9, wherein the selected default property value is automatically chosen with no user input.

16. The method of claim 9, wherein the properties correspond to contact information and are one or more of an address, phone number, email address, web page.

17. The method of claim 9, wherein:

the step for appropriate selecting a default property value based on applying selection criteria to a remote value and a local value, includes;

applying a selection rule prioritizing a high-fidelity device over the low-fidelity device.

18. In a distributed computing system capable of synchronizing properties, a computer program product for implementing a method of providing consistent resolution synchronization conflicts in order to reduce infinite synchronization loops within the distributed system, the computer program product comprising:

one or more computer readable non-transmission type storage media having stored thereon computer executable instructions that, when executed by a processor, can cause the distributed computing system to perform the following;

at a local machine connectable to a plurality of remote devices, and currently connected to at least one of the plurality of remote devices;

receive remote device data that includes a remote property needing to be synchronized with a local property, the remote device data being received from one of the plurality of remote devices currently connected to the local machine, wherein the one of the plurality of remote devices is a low fidelity device that is unable to maintain time date information and the remote device data being low fidelity data;

access local machine data that includes the local property needing to be synchronized with the remote property received from the one of the plurality of remote devices currently connected to the local machine;

determine that a conflict exists between the remote property received from a remote device and the local property of the local machine;

after the determination is made that the conflict exists, and in response to determining that the conflict exists;

utilize a conflict resolution algorithm to generate a unique value from the remote property;

utilize the conflict resolution algorithm to generate a local value from the local property; and

apply data selection criteria to a comparison of the remote value to the local value, and in a manner that eliminates infinite synchronization loops among three or more devices having corresponding properties for synchronization, wherein applying data selection criteria includes;

at a binary bit level, summing bits of the remote value generated from the remote property to generate a first sum;

at a binary bit level, summing bits of the local value generated from the local property to generate a second sum; and

determining which of the first and second sums has a greater value or a lesser value; and

based at least on which of the first sum and second sum has a greater value or a lesser value, selecting the first sum or the second sum, and applying either the remote property or the local property associated with the selected of the first sum or the second sum for synchronization with the local machine or remote device, respectively.

19. The computer program product of claim 18, wherein the conflict resolution algorithm is transitive in that unique values can be generated for a large number of properties.

20. The computer program product of claim 18, wherein the determined property to be used for synchronization is a default value, and a user interface is presented to a user that highlights the default value.

21. The computer program product of claim 20, wherein multiple conflicts exists and multiple default values are generated utilizing the conflict resolution algorithm, and the user is presented with an option within the user interface to apply all the multiple default values.

22. The computer program product of claim 18, wherein the determined property to be used for synchronization is automatically chosen with no user input.

23. The computer program product of claim 18, wherein the conflict resolution algorithm is a hash function and the data selection criteria is a choice of the greatest or least value between the remote value and the local value.

24. The computer program product of claim 18, wherein the conflict resolution algorithm chooses at least a portion of the remote property and a corresponding portion of the local property, and the remote and local values are based on the addition of a number of positive or negative bits, and the data selection criteria is a choice of the greatest or least value between the remote value and the local value.

25. The computer program product of claim 18, wherein the properties correspond to a contact and are one or more of an address, phone number, email address, web page.