Peer-to-peer syncing in a decentralized environment

• US 8,635,209 B2
• Filed: 08/10/2011
• Issued: 01/21/2014
• Est. Priority Date: 06/21/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Freedman, Gordie
• Primary Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US13/206,961
• Publication Number:
  US 20120030173A1
• Time in Patent Office: 895 Days
• Field of Search: None
• US Class Current: 707/722
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

An apparatus and method of synchronizing a datum between a plurality of stores uses version vectors associated with the datum in each store. Each version vector 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 vectors of the datum are compared to determine whether one version vector is subordinate to another version vector. The datum in the store having the subordinate version vector is then replaced with the datum having the dominant version vector. When compared, a conflict resolution by a user is required if the version vectors are not identical, if the version vectors do not have all the same identifiers, and if one version vector does not contain all of the identifiers with equal or greater values of those in the other version vector.

Claims

1. A synchronization method, comprising:

associating a first atom with a first copy of a datum in a first store, the first atom comprising a first identifier that represents a first version vector for the first datum, the first version vector identifying one or more stores where the first copy of the datum was modified;

comparing the first version vector with a second version vector when synchronizing the datum between the first store and a second store by cross-referencing the first version vector represented by the first atom to the second version vector represented by a second atom that comprises a second identifier that represents a second version vector for the second datum, the cross-referencing comprising looking up the first atom and the second atom in a table that maps atoms in the first store to atoms in the second store;

determining from the comparison whether the first version vector is subordinate to or dominant over the second version vector; and

updating the copies of the datum based on the determination.

2. The method of claim 1, wherein if the first version vector is subordinate, the act of updating comprises replacing the first copy of the datum with the second copy of the datum from the second store.

3. The method of claim 2, wherein updating comprises maintaining the second copy of the datum at the second store.

4. The method of claim 1, wherein cross-referencing further comprises maintaining a table at the first store associating one or more version vectors to one or more first atoms consistent with the first scheme and to one or more second atoms consistent with the second scheme.

5. The method of claim 1, wherein comparing comprises:

determining that the second atom is not known at the first store;

receiving the second version vector from the second store in place of the second atom; and

comparing the first version vector associated with the first atom to the second version vector received from the second store.

6. The method of claim 5, further comprising updating the first store by associating the second atom previously unknown at the first store with the first atom at the first store already associated with the second version vector received from the second store.

7. The method of claim 5, further comprising:

determining that the second version vector is not known at the first store;

generating a new first atom at the first store consistent with the first scheme; and

associating the new first atom at the first store with the second atom and the second version vector received from the second store.

8. The method of claim 7, further comprising sending the new first atom to the second store to associate the new first atom with the first atom and the second version vector at the second store.

9. A computer-readable device having computer executable instructions stored thereon for performing a method of synchronizing a datum between a plurality of stores, the computer executable instructions for causing a processor to:

associate a first atom with a first copy of a datum in a first store, the first atom comprising a first identifier that represents a first version vector for the first datum, the first version vector identifying one or more stores where the first copy of the datum was modified;

compare the first version vector with a second version vector when synchronizing the datum between the first store and a second store by cross-referencing the first version vector represented by the first atom to the second version vector represented by a second atom that comprises a second identifier that represents a second version vector for the second datum, the cross-referencing comprising looking up the first atom and the second atom in a table that maps atoms in the first store to atoms in the second store;

determine from the comparison whether the first version vector is subordinate to or dominant over the second version vector; and

update the copies of the datum based on the determination.

10. The computer-readable device of claim 9, further comprising computer executable instructions to update, in part, by replacing the first copy of the datum with the second copy of the datum from the second store wherein if the first version vector is subordinate.

11. The computer-readable device of claim 10, further comprising computer executable instructions to maintain the second copy of the datum at the second store when performing an update to the copies of the datum.

12. The computer-readable device of claim 9, further comprising computer executable instructions to maintain a table at the first store associating one or more version vectors to one or more first atoms consistent with the first scheme and to one or more second atoms consistent with the second scheme when cross-referencing.

13. The computer-readable device of claim 9, further comprising computer executable instructions to:

determine that the second atom is not known at the first store;

receive the second version vector from the second store in place of the second atom; and

compare the first version vector associated with the first atom to the second version vector received from the second store.

14. The computer-readable device of claim 13, further comprising computer executable instructions to associate the second atom previously unknown at the first store with the first atom at the first store already associated with the second version vector received from the second store when performing an update to the copies of the datum.

15. The computer-readable device of claim 13, further comprising computer executable instructions to:

determine that the second version vector is not known at the first store;

generate a new first atom at the first store consistent with the first scheme; and

associate the new first atom at the first store with the second atom and the second version vector received from the second store.

16. A first device capable of synchronizing, the first device comprising:

first memory for storing associations between one or more version vectors and one or more atoms, each of the one or more version vectors identifying one or more stores where the datum was modified, and each of the one or more atoms comprising a separate identifier that represents each of the one or more version vectors;

second memory for storing a first copy of a datum associated with a first version vector and a first of the one or more atoms; and

a processor in communication with the first and second memories and configured to;

cross-reference the first version vector associated with the first atom to a second version vector associated with a second atom when synchronizing the datum between the first device and a second device the second atom comprising an identifier that represents the second version vector, the cross-referencing comprising looking up the first atom and the second atom in a table that maps atoms in the first store to atoms in the second store,

compare the first version vector to the second version vector,

determine from the comparison whether the first version vector is subordinate to or dominant over the second version vector, and

handle the first copy of the datum based on the determination.