Apparatus and method for peer-to-peer N-way synchronization in a decentralized environment

• US 7,523,146 B2
• Filed: 06/21/2005
• Issued: 04/21/2009
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Holt, Joe, Freedman, Gordie, Forstall, Scott
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US11/157,647
• Publication Number:
  US 20060288053A1
• Time in Patent Office: 1,400 Days
• Field of Search: 707200-204
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

An apparatus and method of synchronizing a datum between a plurality of stores is disclosed. A version history is associated with the datum in each store. The version history has one or more entries, and each entry has an identifier and a value. The identifier identifies a store that has modified the datum, and the value indicates a number of modifications to the datum made by the store. When synchronizing the datum between stores, the version histories of the datum are compared to determine whether one version history is subordinate to another version history. The datum in the store having the subordinate version history is then replaced with the datum having the dominant version history. When compared, a conflict resolution by a user is required if the version histories are not identical, if the version histories do not have all the same identifiers, and if one version history does not contain all of the identifiers with equal or greater values of those in the other version history.

Claims

1. A method of synchronizing a datum between a plurality of stores, the method comprising:

associating a version history with the datum in each store, each of the version histories identifying one or more stores that have modified the datum, the version histories comprising a first version history associated with the datum in a first store and a second version history associated with the datum in a second store, the first version history comprising a loser array having one or more losing version histories, if any, that have lost a conflict resolution;

comparing the first and second version histories of the datum in the first and second stores when the datum is synchronized between the first and second stores;

determining whether one of the version histories in one store is subordinate to the version history in another store when comparing the version histories by determining whether the second version history is contained in the loser array of the first version history or whether the second version history is subordinate to one of the one or more losing version histories contained in the loser array of the first version history;

designating the second version history as a subordinate version history and the first version history as a dominant version history if the second version history is contained in the loser array or is subordinate to one of the losing version histories in the loser array; and

replacing the datum in the store having the subordinate version history with the datum in the store having the dominant version history.

2. The method of claim 1, further comprising associating the same version history with the datum in both stores after synchronizing.

3. The method of claim 1, wherein if the second version history is not contained in the loser array or is not subordinate to one of the losing version histories in the loser array, the act of determining comprises determining whether both of the first and second version histories identify all of the same stores as having modified the datum.

4. The method of claim 3, wherein if both of the first and second version histories identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the same stores as having modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history.

5. The method of claim 3, wherein if both version histories do not identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the stores also identified in the other version history;

determining whether all of the same stores identified in the one version history have modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

6. The method of claim 1, further comprising initiating a conflict resolution if the first and second version histories are not identical, if the first and second version histories do not identify all the same stores as modifying the datum, if all of the same stores identified in one of the version histories have not modified the datum as much as or more than the other version history, and if neither of the version histories is contained in the loser array or is subordinate to one of the losing version histories in the loser array of the other version history.

7. The method of claim 1, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the stores that has modified the datum, the value indicating a number of modifications to the datum by the store identified by the identifier.

8. The method of claim 7, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the stores.

9. The method of claim 7, wherein the value comprises a monotonically increasing integer.

10. The method of claim 7, further comprising changing the value of the identifier for a given store when the datum is modified by the given store.

11. The method of claim 7, wherein the act of determining whether one of the first and second version histories is subordinate comprises determining whether the first and second version histories have all the same identifiers.

12. The method of claim 11, wherein the act of determining further comprises:

determining which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designating the one version history with the greater values as the dominant version history and the other version history as the subordinate version history.

13. The method of claim 7, wherein the act of determining whether one of the first and second version histories is subordinate comprises determining whether the first and second version histories do not have all the same identifiers.

14. The method of claim 13, wherein the act of determining further comprises:

determining which one of the version histories contains all of the identifiers of the other version history;

determining whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designating the one version as the dominant version history and the other version history as the subordinate version history if the values of the same identifiers for the one version history are equal to or greater than the values of the same identifiers for the other version history.

15. The method of claim 7, further comprising initiating a conflict resolution if the first and second version histories are not identical, the first and second version histories do not have all the same identifiers, one of the version histories does not contain all of the identifiers with equal or greater values of those in the other version history, and neither of the version histories is contained in the loser array or is subordinate to one of the losing version histories in the loser array of the other version history.

16. The method of claim 1, wherein the act of determining whether one of the first and second version histories is subordinate comprises:

determining whether one of the version histories has lost a conflict resolution to the other version history of the datum; and

designating the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

17. The method of claim 1, further comprising removing redundant losing version histories in the loser array for the second version history.

18. The method of claim 17, wherein the act of removing redundant losing version histories comprises:

comparing portions of the second version history to the loser array of the second version history; and

deleting any losing version history from the loser array that is subordinate to the portions of the second version history.

21. The method of claim 1, further comprising determining whether the first and second version histories are identical and maintaining the versions of the datum and the first and second version histories in the first and second stores.

19. The method of 18, wherein comparing portions of the second version history to the loser array of the second version history occurs when the second version history is updated by a change to the datum in the second store.

20. The method of 18, wherein the act of comparing portions of the second version history to the loser array of the second version history occurs when automatically updating the second version history when synchronizing between stores.

22. A computer-readable medium having computer executable instructions for performing a method of synchronizing a datum between a plurality of stores, the method comprising:

associating a version history with the datum in each store, each of the version histories identifying one or more stores that have modified the datum, the version histories comprising a first version history associated with the datum in a first store and a second version history associated with the datum in a second store, the first version history comprising a loser array having one or more losing version histories, if any, that have lost a conflict resolution;

comparing the first and second version histories of the datum in the first and second stores when the datum is synchronized between the first and second stores;

determining whether one of the version histories in one store is subordinate to the version history in another store when comparing the version histories by determining whether the second version history is contained in the loser array of the first version history or whether the second version history is subordinate to one of the one or more losing version histories contained in the loser array of the first version history;

designating the second version history as a subordinate version history and the first version history as a dominant version history if the second version history is contained in the loser array or is subordinate to one of the losing version histories in the loser array; and

replacing the datum in the store having the subordinate version history with the datum in the store having the dominant version history.

23. The computer-readable medium of claim 22, further comprising associating the same version history with the datum in both stores after synchronizing.

24. The computer-readable medium of claim 22, wherein if the second version history is not contained in the loser array or is not subordinate to one of the losing version histories in the loser array, the act of determining comprises determining whether both of the first and second version histories identify all of the same stores as having modified the datum.

25. The computer-readable medium of claim 24, wherein if both of the first and second version histories identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the same stores as having modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history.

26. The computer-readable medium of claim 24, wherein if both version histories do not identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the stores identified in the other version history;

determining whether all of the same stores identified in the one version history have modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

27. The computer-readable medium of claim 22, further comprising initiating a conflict resolution if the first and second version histories are not identical, if the first and second version histories do not identify all the same stores as modifying the datum, if all of the same stores identified in one of the version histories have not modified the datum as much as or more than the other version history, and if neither of the version histories is contained in the loser array or is subordinate to one of the losing version histories in the loser array of the other version history.

28. The computer-readable medium of claim 22, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the stores that has modified the datum, the value indicating a number of modifications to the datum by the store identified by the identifier.

29. The computer-readable medium of claim 28, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the stores.

30. The computer-readable medium of claim 28, wherein the value comprises a monotonically increasing integer.

31. The computer-readable medium of claim 28, further comprising changing the value of the identifier for a given store when the datum is modified by the given store.

32. The computer-readable medium of claim 28, wherein the act of determining whether one of the first and second version histories is subordinate comprises determining whether the first and second version histories have all the same identifiers.

33. The computer-readable medium of claim 32, wherein the act of determining further comprises:

determining which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designating the one version history with the greater values as the dominant version history and the other version history as the subordinate version history.

34. The computer-readable medium of claim 28, wherein the act of determining whether one of the first and second version histories is subordinate comprises determining whether the first and second version histories do not have all the same identifiers.

35. The computer-readable medium of claim 34, wherein the act of determining further comprises:

determining which one of the version histories contains all of the identifiers of the other version history;

determining whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designating the one version as the dominant version history and the other version history as the subordinate version history if the values of the same identifiers for the one version history are equal to or greater than the values of the same identifiers for the other version history.

36. The computer-readable medium of claim 28, further comprising initiating a conflict resolution if the first and second version histories are not identical, the first and second version histories do not have all the same identifiers, one of the version histories does not contain all of the identifiers with equal or greater values of those in the other version history, and if neither of the version histories is contained in the loser array or is subordinate to one of the losing version histories in the loser array of the other version history.

37. The computer-readable medium of claim 22, wherein the act of determining whether one of the first and second version histories is subordinate comprises:

determining whether one of the version histories has lost a conflict resolution to the other version history of the datum; and

designating the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

38. The computer-readable medium of claim 22, further comprising removing redundant losing version histories in the loser array for the second version history.

39. The computer-readable medium of claim 38, wherein the act of removing redundant losing version histories comprises:

comparing portions of the second version history to the loser array of the second version history; and

deleting any losing version history from the loser array that is subordinate to the portions of the second version history.

42. The computer-readable medium of claim 22, further comprising determining whether the first and second version histories are identical and maintaining the versions of the datum and the first and second version histories in the first and second stores.

40. The computer-readable medium of 39, wherein comparing portions of the second version history to the loser array of the second version history occurs when the second version history is updated by a change to the datum in the second store.

41. The computer-readable medium of 39, wherein the act of comparing portions of the second version history to the loser array of the second version history occurs when automatically updating the second version history when synchronizing between stores.

43. A first device capable of synchronizing a datum across the first device and a second device, the first device comprising:

a user input for modifying the datum;

a first memory for storing the datum;

a second memory for storing a first version history associated with the datum;

a processor configured to;

update the first version history in the second memory to reflect a modification to the datum by the user input of the first device,

compare the first version history to a second version history for the datum on the second device when the first and second devices are synchronized, wherein at least one of the first and second version histories comprises a loser array having one or more losing version histories, if any, that have lost a conflict resolution,

determine whether one of the version histories is subordinate, wherein the processor is configured to determine whether one of the version histories is contained in the loser array of the other version history or is subordinate to one of the losing version histories contained in the loser array of the other version history, and

if the first version history is subordinate, replace the version of the datum in the first memory of the first device with the version of the datum from the second device.

44. The first device of claim 43, wherein the processor is further configured to associate the second version history in the second memory with the datum in the first memory after replacing the version of the datum in the first memory with the version of the datum from the second device.

45. The first device of claim 43, wherein to determine whether one of the version histories is subordinate if neither version history is contained in the loser array or is not subordinate to one of the losing version histories in the loser array of the other version history, the processor is configured to determine whether the first and second version histories identify all of the same devices as having modified the datum.

46. The first device of claim 45, wherein if the first and second version histories identify all of the same devices as having modified the datum, the processor is further configured to:

determine which one of the version histories identifies all of the same devices as having modified the datum as much as or more than the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history.

47. The first device of claim 45, wherein if the first and second version histories do not identify all of the same devices as having modified the datum, the processor is further configured to:

determine which one of the version histories identifies all of the devices identified in the other version history;

determine whether all of the same devices identified in the one version history have modified the datum as much as or more than the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

48. The first device of claim 43, wherein the processor is further configured to initiate a conflict resolution if the first and second version histories are not identical, if the first and second version histories do not identify all the same devices as modifying the datum, if all of the same devices identified in one of the version histories have not modified the datum as much as or more than the other version history, and if neither of the version histories is contained in the loser array or is not subordinate to one of the losing version histories in the loser array of the other version history.

49. The first device of claim 43, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the devices that has modified the datum, the value indicating a number of modifications to the datum by the device identified by the identifier.

50. The first device of claim 49, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the devices.

51. The first device of claim 49, wherein the value comprises a monotonically increasing integer.

52. The first device of claim 49, wherein the processor is further configured to change the value of the identifier for the first device when the datum is modified by the first device.

53. The first device of claim 49, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to determine whether the version histories have all the same identifiers.

54. The first device of claim 53, wherein to determine whether the version histories have all the same identifiers, the processor is further configured to:

determine which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designate the one version history with the greater values as the dominant version history and the other version history as the subordinate version history.

55. The first device of claim 49, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to determine whether the version histories do not have all the same identifiers.

56. The first device of claim 55, wherein to determine whether the version histories do not have all the same identifiers, the processor is further configured to:

determine which one of the version histories contains all of the identifiers of the other version history;

determine whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designate the one version as the dominant version history and the other version history as the subordinate version history if the values of the same identifiers for the one version history are equal to or greater than the values of the same identifiers for the other version history.

57. The first device of claim 49, the processor is further configured to initiate a conflict resolution if the version histories are not identical, the version histories do not have all the same identifiers, one version history does not contain all of the identifiers with equal or greater values of those in the other version history and if the second version history is not contained in the loser array or is not subordinate to one of the losing version histories in the loser array.

58. The first device of claim 43, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to:

determine whether one of the version histories in one device has lost a conflict resolution to the other version history of the datum in the other device; and

designate the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

59. The first device of claim 43, wherein the processor is further configured to remove redundant losing version histories in the loser array from the same version history.

60. The first device of claim 59, wherein to remove redundant losing version histories, the processor is configured to:

compare portions of the version history to the loser array of the same version history; and

delete any losing version history from the loser array that is subordinate to the portions of the same version history.

63. The first device of claim 43, wherein the processor is further configured to determine whether the first and second version histories are identical, and maintain the versions of the datum and the first and second version histories in the devices if identical.

61. The first device of 60, wherein the comparison of portions of the version history to the loser array of the same version history occurs when the version history is updated by a change to the datum in the first device.

62. The first device of 60, wherein the comparison of portions of the version history to the loser array of the same version history occurs when automatically updating the version history when synchronizing between the first and second devices.

64. A method of synchronizing a datum between a plurality of stores, the method comprising:

associating a version history with the datum in each store, each of the version histories identifying one or more stores that have modified the datum;

comparing the version histories of the datum in the stores when the datum is synchronized between the stores;

determining whether one of the version histories in one store is subordinate to the version history in another store when comparing the version histories; and

replacing the datum having a subordinate version history with the datum having a dominant version history,

wherein at least one version history comprises a loser array having one or more losing version histories, if any, that have lost a conflict resolution, and

wherein the method comprises removing redundant losing version histories in the loser array from the at least one version history by—

comparing portions of the at least one version history to the loser array of the at least one version history, and

deleting any losing version history from the loser array that is subordinate to the portions of the at least one version history.

67. The method of claim 64, further comprising associating the same version history with the datum in both stores after synchronizing.

68. The method of claim 64, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether both version histories identify all of the same stores as having modified the datum.

69. The method of claim 64, wherein if both of the version histories identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the same stores as having modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history.

70. The method of claim 69, wherein if both of the version histories do not identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the stores also identified in the other version history;

determining whether all of the same stores identified in the one version history have modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

71. The method of claim 64, further comprising initiating a conflict resolution if the version histories are not identical, if the version histories do not identify all the same stores as modifying the datum, and if all of the same stores identified in one version history have not modified the datum as much as or more than the other version history.

72. The method of claim 64, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the stores that has modified the datum, the value indicating a number of modifications to the datum by the store identified by the identifier.

73. The method of claim 72, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the stores.

74. The method of claim 72, wherein the value comprises a monotonically increasing integer.

75. The method of claim 72, further comprising changing the value of the identifier for a given store when the datum is modified by the given store.

76. The method of claim 72, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether the version histories have all the same identifiers.

77. The method of claim 76, wherein the act of determining further comprises:

determining which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designating the one version history with the greater values as the dominant version history and the other version history as the subordinate version history.

78. The method of claim 72, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether the version histories do not have all the same identifiers.

79. The method of claim 78, wherein the act of determining further comprises:

determining which one of the version histories contains all of the identifiers of the other version history;

determining whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

80. The method of claim 72, further comprising initiating a conflict resolution if the version histories are not identical, the version histories do not have all the same identifiers, and one version history does not contain all of the identifiers with equal or greater values of those in the other version history.

81. The method of claim 64, wherein the act of determining whether one of the version histories in one store is subordinate comprises:

determining whether one of the version histories in one store has lost a conflict resolution to the version history of the datum in the other store; and

designating the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

82. The method of claim 64, wherein the act of determining whether one of the version histories in one store is subordinate comprises:

determining whether one of the version histories is contained in the loser array of the other version history or whether one of the version histories is subordinate to a subordinate version history contained in the loser array of the other version history; and

designating the one determined version history as the subordinate version history and the other version history as the dominant version history.

65. The method of 64, wherein comparing portions of the version history to the loser array of the at least one version history occurs when the at least one version history is updated by a change to the datum in the store.

66. The method of 64, wherein the act of comparing portions of the at least one version history to the loser array of the same version history occurs when automatically updating the at least one version history when synchronizing between stores.

83. A computer-readable medium having computer executable instructions for performing a method of synchronizing a datum between a plurality of stores, the method comprising:

associating a version history with the datum in each store, each of the version histories identifying one or more stores that have modified the datum;

comparing the version histories of the datum in the stores when the datum is synchronized between the stores;

determining whether one of the version histories in one store is subordinate to the version history in another store when comparing the version histories; and

replacing the datum having a subordinate version history with the datum having a dominant version history,

wherein at least one version history comprises a loser array having one or more losing version histories, if any, that have lost a conflict resolution, and

wherein the method comprises removing redundant losing version histories in the loser array from the at least one version history by—

comparing portions of the at least one version history to the loser array of the at least one version history, and

deleting any losing version history from the loser array that is subordinate to the portions of the at least one version history.

86. The computer-readable medium of claim 83, further comprising associating the same version history with the datum in both stores after synchronizing.

87. The computer-readable medium of claim 83, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether both of the version histories identify all of the same stores as having modified the datum.

88. The computer-readable medium of claim 87, wherein if both of the version histories identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the same stores as having modified the datum as much as or more than the other version histories; and

designating the one version history as the dominant version history and the other version history as the subordinate version history.

89. The computer-readable medium of claim 87, wherein if both of the version histories do not identify all of the same stores as having modified the datum, the act of determining further comprises:

determining which one of the version histories identifies all of the stores also identified in the other version history;

determining whether all of the same stores identified in the one version history have modified the datum as much as or more than the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history if all of the same stores identified in the one version history have modified the datum as much as or more than the other version history.

90. The computer-readable medium of claim 83, further comprising initiating a conflict resolution if the version histories are not identical, if the version histories do not identify all the same stores as modifying the datum, and if all of the same stores identified in one version history have not modified the datum as much as or more than the other version history.

91. The computer-readable medium of claim 83, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the stores that has modified the datum, the value indicating a number of modifications to the datum by the store identified by the identifier.

92. The computer-readable medium of claim 91, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the stores.

93. The computer-readable medium of claim 91, wherein the value comprises a monotonically increasing integer.

94. The computer-readable medium of claim 91, further comprising changing the value of the identifier for a given store when the datum is modified by the given store.

95. The computer-readable medium of claim 91, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether the version histories have all the same identifiers.

96. The computer-readable medium of claim 95, wherein the act of determining further comprises:

determining which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designating the one version history as the dominant version history and the other version history as the subordinate version history.

97. The computer-readable medium of claim 91, wherein the act of determining whether one of the version histories in one store is subordinate comprises determining whether the version histories do not have all the same identifiers.

98. The computer-readable medium of claim 97, wherein the act of determining further comprises:

determining which one of the version histories contains all of the identifiers of the other version history;

determining whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designating the one version as the dominant version history and the other version history as the subordinate version history if the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history.

99. The computer-readable medium of claim 91, further comprising initiating a conflict resolution if the version histories are not identical, the version histories do not have all the same identifiers, and one version history does not contain all of the identifiers with equal or greater values of those in the other version history.

100. The computer-readable medium of claim 83, wherein the act of determining whether one of the version histories in one store is subordinate comprises:

determining whether one of the version histories in one store has lost a conflict resolution to the version history of the datum in the other store; and

designating the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

101. The computer-readable medium of claim 83, wherein the act of determining whether one of the version histories in one store is subordinate comprises:

determining whether one of the version histories is contained in the loser array of the other version history or whether one of the version histories is subordinate to a subordinate version history contained in the loser array of the other version history; and

designating the one determined version history as the subordinate version history and the other version history as the dominant version history.

84. The computer-readable medium of 83, wherein comparing portions of the at least one version history to the loser array of the at least one version history occurs when the at least one version history is updated by a change to the datum in the store.

85. The computer-readable medium of 83, wherein the act of comparing portions of the at least one version history to the loser array of the at least one version history occurs when automatically updating the at least one version history when synchronizing between stores.

102. A first device capable of synchronizing a datum across the first device and a second device, the first device comprising:

a user input for modifying the datum;

a first memory for storing the datum;

a second memory for storing a first version history associated with the datum;

a processor configured to;

update the first version history in the second memory to reflect a modification to the datum by the user input of the first device,

compare the first version history to a second version history for the datum on the second device when the first and second devices are synchronized,

determine whether the first version history is subordinate to the second version history, and

if the first version history is subordinate, replace the version of the datum in the first memory of the first device with the version of the datum from the second device,

wherein at least one version history comprises a loser array having one or more losing version histories, if any, that have lost a conflict resolution, and

wherein the processor is configured to remove redundant losing version histories in the loser array from the at least one version history, the processor being configured to—

compare portions of the at least one version history to the loser array of the at least one version history, and

delete any losing version history from the loser array that is subordinate to the portions of the at least one version history.

105. The first device of claim 102, wherein the processor is further configured to associate the second version history in the second memory with the datum in the first memory after replacing the version of the datum in the first memory with the version of the datum from the second device.

106. The first device of claim 102, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to determine whether the first and second version histories identify all of the same devices as having modified the datum.

107. The first device of claim 106, wherein to determine whether the first version history is subordinate to the second version history if the first and second version histories identify all of the same devices as having modified the datum, the processor is further configured to:

determine whether all of the same devices identified in one of the version histories have modified the datum as much as or more than the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history.

108. The first device of claim 106, wherein to determine whether the first version history is subordinate to the second version history if the first and second version histories do not identify all of the same devices as having modified the datum, the processor is further configured to:

determine whether all of the devices identified in one version history are also identified in the other version history;

determine whether all of the same devices identified in the one version history have modified the datum as much as or more than the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history.

109. The first device of claim 102, wherein the processor is further configured to initiate a conflict resolution if the first and second version histories are not identical, if the first and second version histories do not identify all the same devices as modifying the datum, and if all of the same devices identified in one version history have not modified the datum as much as or more than the other version history.

110. The first device of claim 102, wherein each version history comprises one or more entries, each entry having an identifier and a value, the identifier identifying one of the devices that has modified the datum, the value indicating a number of modifications to the datum by the device identified by the identifier.

111. The first device of claim 110, wherein the identifier comprises a machine identification, a globally unique identification file, a network address, an Internet protocol address, an Ethernet address, or a globally unique identification differentiating the devices.

112. The first device of claim 110, wherein the value comprises a monotonically increasing integer.

113. The first device of claim 110, wherein the processor is further configured to change the value of the identifier for the first device when the datum is modified by the first device.

114. The first device of claim 110, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to determine whether the version histories have all the same identifiers.

115. The first device of claim 114, wherein to determine whether the version histories have all the same identifiers, the processor is further configured to:

determine which one of the version histories has values for the same identifiers that are greater than the values of the same identifiers of the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history.

116. The first device of claim 110, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to determine whether the version histories do not have all the same identifiers.

117. The first device of claim 116, wherein to determine whether the version histories do not have all the same identifiers, the processor is further configured to:

determine which one of the version histories contains all of the identifiers of the other version history;

determine whether the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history; and

designate the one version history as the dominant version history and the other version history as the subordinate version history if the values of the same identifiers for the one version history are equal to or greater than values of the same identifiers for the other version history.

118. The first device of claim 110, the processor is further configured to initiate a conflict resolution if the version histories are not identical, the version histories do not have all the same identifiers, and one version history does not contain all of the identifiers with equal or greater values of those in the other version history.

119. The first device of claim 102, wherein to determine whether the first version history is subordinate to the second version history, the processor is configured to:

determine whether one of the version histories in one device has lost a conflict resolution to the version history of the datum in the other device; and

designate the one version that has lost the conflict resolution as the subordinate version history and the other version history as the dominant version history.

120. The first device of claim 102, wherein to determine whether the first version history is subordinate to the second version history, the processor is further configured to:

determine whether one of the version histories is contained in the loser array of the other version history or whether one of the version histories is subordinate to a subordinate version history contained in the loser array of the other version history; and

designate the one determined version history as the subordinate version history and the other version history as the dominant version history.

103. The first device of 102, wherein the comparison of portions of the first version history to the loser array of the same first version history occurs when the first version history is updated by a change to the datum in the first device.

104. The first device of 102, wherein the comparison of portions of the first version history to the loser array of the same first version history occurs when automatically updating the first version history when synchronizing between the first and second devices.