An Apple patent (number 20110264623) for a method and system for using global equivalency sets to identify data during peer-to-peer synchronization has appeared at the US Patent & Trademark Office.
It involves systems and methods for synchronization including the use of a global equivalency identification datum or set of datum. A universally unique identification datum may be associated with each independently created associated data set. In some embodiments, a synchronization server software element may be responsible for maintaining synchronization for a plurality of clients, including software elements or devices.
A record believed to be new by the software elements may verify that the record is actually new. In some embodiments, verification of the record’s newness involves assuming that the local ID is a global identification datum and comparing that datum to the all the sets of datum that the Sync-Server knows about. The synchronization server software element may use a table to hold information for all of the records known to that element. In some embodiments these records may have been deleted in the past. The inventors are Gordie Freedman and Bruce D. Nilo.
Here’s Apple’s summary of the invention: “The embodiments described herein relate to the use of a global equivalency identification datum or set of datum (hereinafter ‘GID’) as an aid to synchronization systems and methods. In a very simple embodiment, the synchronization problems discussed above are solved by associating a universally unique identification datum (hereinafter ‘UUID’) with each independently created associated data set (e.g. structured data record). For example, in a specific embodiment relating to PIM data, upon creating a record for Joe Doe in a first peer device, the record is assigned a GID, which for purposes of this example we shall call GID1. If an analogous record for the same Joe Doe is created on a second peer device, that record is also assigned a GID, which for purposes of this example, we shall call GID2.
“Further, since many embodiments use a UUID as a GID, the GID1 is certainly unique or different from the GID2. If in our example, the name property is the identity key, then upon synchronizing the first peer and the second peer, the two independently created Joe Doe records will be associated as corresponding records of the “same” data set. Finally, according to some embodiments of the invention, as a result of such synchronization, the GIDs of both Joe Doe records will become a Global Equivalency Set (‘GES’) comprised of GID1 and GID2.
“A more complex embodiment may contemplate the software elements in a typical synchronization system and the interaction between those elements. For example, in some embodiments, a synchronization server (‘Sync-Sever’) software element may be responsible for maintaining synchronization for a plurality of clients; some clients potentially being software elements (e.g. a contact manager program), other clients potentially being devices such as phones or PDAs. Each client represents a vehicle for any one or more of the following: viewing records or portions thereof; editing records or portions thereof; adding records or portions thereof; and deleting records or portions thereof.
“Furthermore, for the sake of clarity and without limitation, we are generally discussing records as a set of associated properties. For example, a contact record may contain properties or fields such as name, address and phone number. Such a contact may also contain metadata fields such as date of last edit, identity of creator client or the GID datum itself may be carried as a property to a record.
“In many embodiments, new records are created by clients, and the creator client assigns a local ID datum to the record. When that creator client synchronizes with the Sync-Server, the new record is pushed to the Sync-Server as a new record. Since the Sync-Server cannot be certain that the record is truly new, the Sync-Server will embark upon a process to verify the newness of the record. It is important to realize that while the creator client believes the new record is indeed new, it may not actually be truly new.
“This is because, the Sync-Server may already know about a corresponding record that was either (i) independently created by another client (e.g. the same contact information independently entered into two different peers of the relevant group of syncing systems); or (ii) originally a duplicate of the creator clients new record that somewhere in the peer system lost its ability to be readily identified as such (through user and/or system manipulations or anomalies).
“In some embodiments, verification of the record’s newness involves assuming that the local ID is a GID and comparing that datum to the all GID data sets that the Sync-Server knows about. For example, the Sync-Server may use a table to hold GID information for all of the records known to that Sync-Server, which according to some embodiments may comprise records that have been deleted in the past. If the Sync-Server does not find the GID in its records, then the new record may be treated as truly new (subject to any other checks against the Sync-Server database such as an identity key check). However, if the GID is found in the Sync-Server’s records, then the handling of the pseudo new record will be according to the information found on the Sync-Server with respect to that GID.
“For example, the Sync-Server records may indicate that the record has been previously deleted; and some embodiments may treat the pseudo new record as deleted and inform the creator client to delete it, while other embodiments may enter a conflicts resolution process to determine user intent either expressly or by inference. In some embodiments, when presented with a new record from a client, if the Sync-Server does not find a GID match, the Sync-Server will proceed to check the new record’s identity keys against the Sync-Server’s relevant database or table.
“If there is no GID match but there is an identity key match, some embodiments will associate the two records and update the GES for that record in each system (the client and the Sync-Server) to reflect two GID datums (one for the original record on the Sync-Server and one for the new record coming from the client). These actions may also be taken if the identity keys have substantially the same value. In various embodiments, substantially the same value may be defined as having a particular number or pattern of common values.
“For example, if a name property is the identity key, values may be defined as substantially the same value if the last name of each value is identical and the first name of one value is a common nickname or an alternative spelling of the first name of another name property value. Other variations of this concept will be apparent to those of skill in the art. Equivalent values may be pre-configured and stored, may be dynamically determined according to an algorithm, or a combination of the two. In addition to updating the GID properties of each system, any conflict between the properties of the associated records will be resolved. Of course, each system may have a different scheme for property-level conflict resolution, and many such schemes are known in the art and may be included in the patents and patent applications incorporated herein.”
— Dennis Sellers