System and methods for communicating between multiple devices for synchronization

• US 6,487,560 B1
• Filed: 05/13/1999
• Issued: 11/26/2002
• Est. Priority Date: 10/28/1998
• Status: Active Grant

• Current Assignee: Intellisync Corporation (Nokia Corporation)
• Original Assignee: Starfish Software, Inc. (Nokia Corporation)
• Inventors: Dube, Bryan, LaRue, Chris, Yu, Chiahua George
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/311,781
• Time in Patent Office: 1,293 Days
• Field of Search: 709/226, 709/217, 709/225, 707/10, 707/104, 707/203, 707/8, 707/201, 707/102
• US Class Current: 707/625
• 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: Y10S 707/922 Communications
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• 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

A system and methods for synchronizing information in datasets via a communication medium are provided that are suitable for synchronizing even across communication mediums that are susceptible to high latency, non-FIFO (non-First-In-First-Out) delivery order, or other adverse characteristics. According to an aspect of the invention, a computer-implemented method is for synchronizing user data in a first dataset with user data in at least a second dataset via a communication medium. The user data in the first dataset and the user data in the second dataset are capable of having been independently modified prior to the synchronization. The method includes sending a dataset change from the first dataset, receiving the dataset change via the communication medium, and determining whether the received dataset change, hereinafter referred to as the just-received change, was sent earlier than another dataset change, hereinafter referred to as the previously-received change, from the first dataset that was received earlier than the receiving step. The method further includes performing synchronization of the first and the second datasets based at least in part on the determining step. The performing step includes refraining from propagating the just-received change into the second dataset, if the just-received change is determined in the determining step to have been sent earlier than the previously-received change. The performing step further includes propagating the just-received change into the second dataset at least to an extent needed for reconciling the just-received change with the second dataset, otherwise.

Claims

1. A computer-implemented method for synchronizing user data in a first dataset at a first device with user data in a second dataset at a second device, wherein the first dataset and the second dataset are each capable of having been changed independently of any synchronization of the first and second datasets, the method including synchronizing changes from the first device to the second device and synchronizing changes from the second device to the first device, the method comprising:

establishing a first communication session between the first and the second devices;

transmitting first communications, reflective of changes that have been made to the first dataset, to the second device via the first communication session, but not transmitting communications reflective of changes that have been made to the second dataset during the first communication session;

intentionally terminating the first communication session;

modifying the second dataset, based on the first communications, at least to an extent toward reconciling the first and second datasets;

after the terminating step, establishing a second communication session between the first and the second devices;

transmitting second communications, reflective of changes that have been made to the second dataset, to the first device via the second communication session, but not transmitting communications reflective of changes that have been made to the first dataset during the second communication session; and

modifying the first dataset, based on the second communications, at least to an extent toward reconciling the first and second datasets.

2. The method of claim 1 wherein the first device is a portable personal organizer device that is capable of distant wireless communication, and the first and second communication sessions are distant wireless communication sessions.

3. The method of claim 1 wherein the steps of establishing the first and second communication sessions comprise establishing socket-based communication sessions over the Internet as the first and second communication sessions.

4. The method of claim 1 wherein the step of transmitting the first communications is executed without necessarily triggering eventual execution of the step of establishing the second communication session, and the method further comprises accepting user input for initiating the steps of establishing the second communication session, transmitting the second communications, and modifying the first dataset.

5. The method of claim 1, further comprising determining, as the changes that have been made to the second dataset, changes that are conflict-free with respect to the changes that have been made to the first dataset.

6. A computer-implemented method for synchronizing user data in a first dataset with user data in a second dataset, wherein the first dataset and the second dataset are each capable of having been changed independently of each other, and the first dataset resides at a first device, and the second dataset resides at a second device, the method comprising:

sending dataset changes of the first dataset from the first device;

receiving the dataset changes of the first dataset and propagating the received dataset changes of the first dataset into the second dataset, at least to an extent for reconciling with the second dataset;

sending dataset changes of the second dataset to the first device, without any communication of dataset changes between the first and second devices between the two sending steps, wherein the two sending steps are intentionally undertaken without both being part of any single communication session; and

receiving and propagating the dataset changes of the second dataset into the first dataset, at least to an extent for reconciling with the first dataset.

7. The method of claim 6 further comprising, after the step of sending the dataset changes of the first dataset and before the step of receiving and propagating the dataset changes of the second dataset:

accepting user input for altering the first dataset; and

altering the first dataset based on the user input.

8. The method of claim 7 wherein the dataset changes of the second dataset have been determined to be conflict-free with a previously-known version of the first dataset, and the step of receiving and propagating the dataset changes of the second dataset into the first dataset comprises propagating the dataset changes of the second dataset into the first dataset to overwrite only data of records of the first dataset that reflect the previously-known version of the first dataset.

9. The method of claim 6 wherein:

the step of sending the dataset changes of the first dataset is before the step of sending the dataset changes of the second dataset; and

the step of sending the dataset changes of the first dataset comprises sending the dataset changes of the first dataset without triggering eventual execution of the step of sending dataset changes of the second dataset.

10. The method of claim 9 wherein the step of sending the dataset changes of the first dataset comprises:

sending a first group of dataset changes of the first dataset;

permitting user-modification of the first dataset; and

sending a second group of dataset changes of the first dataset arbitrarily later than the sending of the first group.

11. The method of claim 9 further comprising requesting the dataset changes of the second dataset independently of any sending of dataset changes of the first dataset, wherein the step of sending the dataset changes of the second dataset is in response to the requesting step.

12. The method of claim 6 wherein:

the step of sending the dataset changes of the first dataset comprises sending the dataset changes of the first dataset via a wireline or wireless communication network; and

the step of receiving and propagating the dataset changes of the first dataset comprises receiving the dataset changes of the first dataset via the wireline or wireless communication network.

13. The method of claim 12 wherein the wireline or wireless communication network is a cellular wireless communication network.

14. The method of claim 12 wherein the method further comprises acknowledging receipt of the dataset changes of the first dataset, and the step of sending the dataset changes of the first dataset comprises:

sending at least a first dataset change from the first device, wherein the first dataset change involves a first record of the first dataset; and

sending at least a second dataset change from the first device prior to any receipt at the first device of an acknowledgment from the acknowledging step that the sent first dataset change has been received at the second device, wherein the second dataset change involves a second record of the first dataset.

15. The method of claim 12 wherein the step of sending the dataset changes of the first dataset comprises sending all the dataset changes of the first dataset within a single transmission.

16. The method of claim 6 wherein the step of sending the dataset changes of the first dataset comprises sending the dataset changes of the first dataset in multiple transmissions.

17. The method of claim 16 wherein the step of receiving and propagating the dataset changes of the first dataset comprises propagating received dataset changes from one of the multiple transmissions into the second dataset, at least to an extent for reconciling with the second dataset, without regard to whether all earlier-sent transmissions of the multiple transmissions have been successfully received.

18. The method of claim 6 wherein:

the dataset changes of the second dataset include all changes necessary to bring the second dataset into synchronization with the version of the first dataset as last-known to the second device;

the method further comprises acknowledging receipt of the dataset changes of the second dataset; and

the step of sending the dataset changes of the second dataset comprises sending any of the dataset changes of the second dataset without regard for whether any other of the dataset changes of the second dataset has been acknowledged as received.

19. The method of claim 6 wherein the any single communication session consists of a bidirectional communication session over a bidirectional socket connection.

20. The method of claim 19 wherein the sending steps comprise sending connectionless messages containing dataset changes.

21. The method of claim 6 further comprising, prior to the step of sending the dataset changes of the first dataset, determining the dataset changes of the first dataset, wherein the dataset changes of the first dataset reflect all records of the first dataset that have been modified since the records were known to the second device.

22. The method of claim 21 wherein the determining step comprises determining a dataset change to reflect a record, as one of the dataset changes of the first dataset, if the record has been modified since a dataset change reflecting the record was earlier sent and the earlier-sent dataset change was confirmed as received by the second device, wherein the dataset change to reflect the record is determined even if:

one or more dataset changes reflecting the record have been sent after a most recent modification of the record; and

the one or more dataset changes have not yet been confirmed as received by the second device.

23. The method of claim 22 wherein the determining step further comprises refraining from determining any dataset change to reflect the record, if the record is unmodified since either:

a dataset change reflecting the record was earlier sent to the second device and the earlier-sent dataset change was confirmed as received by the second device;

or

a dataset change reflecting the record was earlier received from the second dataset and fully propagated into the first dataset.

24. The method of claim 6 wherein the first device includes a wireless telephone, and the sending steps comprise sending wireless signals.

25. The method of claim 24 wherein the first dataset includes user contact information and user calendar information.

26. The method of claim 6 wherein the step of sending the dataset changes of the first dataset comprises sending the dataset changes of the first dataset via a communication medium that is susceptible to communication latency of greater than about a minute.

27. A system for synchronizing user data in a first dataset with user data in a second dataset via a communication medium, wherein the first dataset and the second dataset are each capable of having been changed independently of each other, the system comprising:

means for sending dataset changes of the first dataset;

means for receiving the dataset changes of the first dataset via the communication medium and propagating the received dataset changes of the first dataset into the second dataset, at least to an extent for reconciling with the second dataset;

means for sending dataset changes of the second dataset via the communication medium, without being within any same communication session as the sending of the dataset changes of the first dataset; and

means for receiving and propagating the dataset changes of the second dataset into the first dataset, at least to an extent for reconciling with the first dataset.

28. The system of claim 27 wherein the means for receiving and propagating the dataset changes of the second dataset is configured to allow the user to have modified the first dataset prior to propagating of the dataset changes of the second dataset into the first dataset by the means for receiving and propagating the dataset changes of the second dataset and after sending of the dataset changes of the first dataset by the means for sending dataset changes of the first dataset.

29. The system of claim 27 wherein:

the first dataset resides with a first device, and the second dataset resides with a second device, and the first and second devices are capable of communicating via the communication medium at least occasionally;

the system further comprises means for acknowledging receipt of the dataset changes of the first dataset; and

the means for sending the dataset changes of the first dataset is configured to send at least a first dataset change involving a first record from the first device and to send at least a second dataset change involving a second record from the first device prior to any receipt at the first device of an acknowledgment that the sent first dataset change has been received at the second device.

30. The system of claim 29 wherein the communication medium includes an Internet-Protocol-based messaging network.

31. The system of claim 27 wherein the means for receiving the dataset changes of the first dataset and propagating the received dataset changes is configured to propagate received dataset changes, at least to an extent for reconciling with the second dataset, without regard to whether all dataset changes that were sent for the synchronizing, by the means for sending the dataset changes of the first dataset, have been successfully received.

32. In an information processing system, a method for synchronizing a first dataset in a first device with a second dataset in a second device via a communication medium, wherein the first and second datasets each includes user information, and the first and second datasets are each capable of having been changed independently each other, the method comprising:

communicating messages between the first device and the second device via the communication medium using only a number of plies, wherein the messages are indicative of dataset values for an amount of changed data, the number of plies, absent communication error, is largely independent of the amount of changed data, and the communicating step comprises confirming receipt by the first device of received messages from the second device that are indicative of dataset values; and

modifying the first and the second datasets based on the communicated messages to synchronize the first and second datasets.

33. The method of claim 32 wherein the communication medium includes a wireless communication network.

34. The method of claim 33 wherein the modifying step comprises modifying the second dataset to include dataset values indicated by received messages from the first device, regardless of whether all messages from the first device for the synchronizing have been received by the second device.

35. The method of claim 32 wherein the amount of changed data involves a number of data records, and the number of plies used, absent communication error, needs grow less than linearly, if at all, with the number of data records involved.

36. The method of claim 32 wherein the number of plies used, absent communication error, is no greater than a constant number, regardless of the amount of changed data.

37. The method of claim 32 wherein the constant number is no greater than four.

38. The method of claim 32 wherein the communicating step comprises:

sending from the first device a first ply of messages that are indicative of dataset values of the first dataset; and

sending from the second device a second ply of messages that are indicative of dataset values of the second dataset.

39. The method of claim 38 wherein the step of sending the second ply of messages comprises sending, as a part of the second ply of messages, messages that confirm receipt of messages, from among the first ply of messages, that were received by the second device.

40. The method of claim 38 wherein the step of sending the first ply of messages comprises sending all messages of the first ply within a single transmission.

41. The method of claim 38 wherein the step of sending the first ply of messages comprises sending messages of the first ply in multiple transmissions.

42. The method of claim 41 wherein the multiple transmissions include a wireless transmission.

43. The method of claim 38 wherein the communicating step further comprises sending from the first device a third ply of messages, wherein the third ply of messages include information for mapping data records of the first dataset to data records of the second dataset.

44. The method of claim 32 wherein the modifying step comprises modifying the second dataset to include dataset values indicated by received messages of a ply, from the first device, regardless of whether other messages of the ply have been successfully received.

45. The method of claim 32 wherein the communicating step comprises communicating the messages within a point-to-point, real-time, full-duplex connection.

46. The method of claim 32 wherein the communicating step comprises communicating the messages in a connectionless, message-based manner.

47. The method of claim 32 further comprising determining data in the second dataset having values that were never confirmed as indicated to, and received by, the first device, wherein the communicating step comprises communicating messages indicative of dataset values for the determined data to the first device.

48. The method of claim 47 further comprising storing confirmation information at the second device regarding data of the second dataset having values confirmed in the confirming step as having been received by the first device, wherein the confirmation information is for use in a future synchronization for determining messages to communicate to the first device.

49. The method of claim 32 wherein the communication medium includes a wireline communication network.

50. The method of claim 32 wherein the communicating step comprises confirming receipt by the second device of received messages indicative of dataset values of the first dataset.

51. The method of claim 32 wherein the communication medium is susceptible to communication latency of greater than about a minute.

52. A system for synchronizing a first dataset in a first device with a second dataset in a second device via a communication medium, wherein the first and second datasets each includes user information, and the first and second datasets are each capable of having been changed independently of the other of the first and second datasets, the system comprising:

means for communicating messages indicative of dataset values between the first device and the second device via the communication medium using only a number of plies, wherein the number of plies used grows less than linearly, if at all, with the number of data records involved, and the communicating step comprises confirming receipt by the first device of received messages indicative of dataset values; and

means for modifying the first and the second datasets based on the messages indicative of dataset values to synchronize the first and second datasets.

53. The system of claim 52 wherein the means for modifying comprises means for modifying the second dataset to include dataset values indicated by received messages from the first device, regardless of whether all messages from the first device for the synchronizing have been received by the second device.

54. A method for synchronizing a first dataset in a first device with a second dataset in a second device, using a synchronizer, wherein the first dataset and the second dataset are each capable of having been changed independently of any synchronization to the first and second datasets, the method including synchronizing changes from the first device to the second device and synchronizing changes from the second device to the first device, the method comprising:

establishing a first communication session between the first device and the second device;

transmitting first communications, reflective of changes that have been made to the first dataset, to the synchronizer via the first communication session, but not transmitting communications reflective of changes that have been made to the second dataset during the first communication session;

intentionally terminating the first communication session;

allowing additional changes to be made to the first dataset after the first communications are transmitted;

modifying the second dataset, based on the first communications, at least to an extent toward reconciling the first and second datasets;

after the terminating step, establishing a second communication session between the first and the second devices;

transmitting second communications, reflective of changes that have been made to the second dataset, to the first device via the second communication session, but not transmitting communications reflective of changes that have been made to the first dataset during the second communication session; and

determining, for each of the changes that have been made to the second dataset and that have been reflected in the second communications, whether a recent change has been made to a corresponding record in the first dataset since the first communications were transmitted, and;

if a recent change has not been made to a corresponding record since the first communications were transmitted, implementing the change that has been made to the second dataset into the first dataset;

or

if a recent change has been made to a corresponding record since the first communications were transmitted, performing special handling of the change that has been made to the second dataset to resolve any possible conflicts with the recent change.

55. The method of claim 54, wherein the step of performing special handling of the change that has been made to the second dataset involves performing a conflict resolution between the change that has been made to the second dataset and the recent change to the corresponding record.

56. The method of claim 54, wherein the step of performing special handling of the change that has been made to the second dataset involves discarding the change that has been made to the second dataset and relying on the synchronizer to perform a conflict resolution at a later time between the recent change to the corresponding record and the change that has been made to the second dataset.