Wide area peer-to-peer synching in a decentralized environment

• US 7,760,767 B2
• Filed: 01/05/2007
• Issued: 07/20/2010
• Est. Priority Date: 01/05/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Freedman, Gordie, Paterson, Toby, Nilo, Bruce
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Liu; Jung
• Application Number:
  US11/620,618
• Publication Number:
  US 20080165807A1
• Time in Patent Office: 1,292 Days
• Field of Search: 370/503, 370/401, 370/400, 370/509
• US Class Current: 370/503
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A system and method are disclosed for synchronizing data between devices and more particularly for synchronizing data between a plurality of peer-to-peer devices in a decentralized environment where no one device stores the most “recent” or “true” version of the data. Embodiments of the invention relate concepts of discovering synchronizing peers, communication between peers using special techniques, and using a way station concept as an aid for both discovery and synchronization between peers that are not simultaneously available.

Claims

1. A method of synchronizing a first peer with a second peer and a third peer, the method comprising the steps of:

appointing said first peer as an instigator of a synchronization session;

said first peer making an indication to said second and third peers;

in response to said indications, said second and third peers performing first local synchronizations and generating respectively a second peer change set and a third peer change set;

transmitting said second peer change set from said second peer to said first peer;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said second and third peer change sets from the second and third peers;

performing a second local synchronization at the first peer using the second and third peer change sets;

in response to said second local synchronization, said first peer producing a first return change set for said second peer and a second return change set for said third peer; and

said second peer and said third peer each performing a third local synchronization respectively using said first return change set and said second return change set.

2. The method of claim 1, wherein said first peer discovers a new peer through synchronization with said second peer.

3. The method of claim 1, wherein said first peer discovers a new peer through interaction with a way station software module.

4. The method of claim 1, wherein said first peer presents a user interface to a user regarding the discovery of a new peer.

5. The method of claim 4, wherein said user interface regarding the discovery of the new peer system accepts input from a touch sensing system.

7. The method of claim 5, wherein said user interface regarding the discovery of the new peer system accepts fusion input, said fusion input comprising input from a touch sensing system combined with at least one other type of input.

8. The method of claim 1, wherein said first peer uses Bonjour techniques to discover a new peer.

9. The method of claim 1, wherein said first peer uses Gnutella-type techniques to discover a new peer.

10. The method of claim 3, wherein said first peer communicates with the way station software module to obtain information regarding the new peer.

11. The method of claim 10, wherein said way station software module runs on a hardware platform different from said first peer.

12. The method of claim 10, wherein said way station software module is associated with a directory data structure, said directory data structure comprising information regarding said sync system peers.

13. The method of claim 12, wherein said directory data structure comprises information regarding users of peer systems.

14. The method of claim 12, wherein said directory data structure comprises information regarding software or hardware platforms of said peer systems.

15. The method of claim 1, wherein said second peer and said third peer do not propagate additional change sets in response to performing the second local synchronization respectively using said first return change set and said second return change set.

16. The method of claim 1, wherein the step of transmitting said second peer change is preceded by the additional step of storing said second peer change set.

17. The method of claim 1, wherein the step of appointing said first peer as an instigator comprises the substeps of:

said first peer and said second peer both essentially simultaneously attempting to instigate a synchronization session;

said first peer learning about the activity of said second peer;

said first peer ceasing its instigating activity; and

said first peer, after ceasing its instigating activity, waiting a time period and after said time period, instigating a subsequent synchronization session.

18. The method of claim 17, wherein said time period is derived from a randomly determined data.

19. The method of claim 1, wherein said step of receiving said second and third change sets comprises the step of using NAT traversal techniques.

20. The method of claim 1, wherein said step of receiving said second and third peer change sets comprises the additional step of sending receipt acknowledgement indications respectively to said second peer and said third peer.

21. The method of claim 1, wherein:

the step of transmitting said second peer change is preceded by the additional step of storing said second peer change set;

said step of receiving said second peer change set comprises the additional step of sending receipt acknowledgement indications to said second peer; and

said second peer receiving said acknowledgement indication and in response thereto deleting said second peer change set.

6. The method of 5, wherein said accepted input comprises at least one gesture involving multiple simultaneous points of contact with the touch sensing system.

22. A method of synchronizing a first peer with a second peer and a third peer, wherein said second peer and said first peer communicate only by leaving messages with a way station peer, the method comprising the steps of:

appointing said first peer as an instigator for a synchronization session;

said first peer making an indication to said third peer;

said first peer leaving an indication message for said second peer on said way station peer;

in response said indication, said third peer performing a first local synchronization and generating a third peer change set;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said third peer change set and using said third peer change set to perform a second local synchronization;

after said second local synchronization, said second peer receiving said indication message via said way station peer;

in response to said indication message, said second peer performing a third local synchronization and generating a second peer change set; and

said first peer performing a fourth local synchronization using said second peer change set.

23. The method of claim 22, comprising the additional step of said second peer leaving a second change set message on said way station peer.

24. The method of claim 23, comprising the additional step of said first peer receiving said second change set message and then communicating directly with said second peer to acquire said second peer change set.

25. The method of claim 22, wherein said second change set message comprises said second peer change set.

26. A method of synchronizing a first peer with a second peer and a third peer, wherein said second peer and said first peer communicate by leaving messages with a way station peer, the method comprising the steps of:

appointing said first peer as an instigator for a synchronization session;

said first peer making an indication to said third peer;

said first peer leaving an indication message for said second peer on said way station peer;

in response said indication, said third peer performing a first local synchronization and generating a third peer change set;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said third peer change set and using said third peer change set to perform a second local synchronization;

after said second local synchronization, said second peer receiving said indication message via said way station peer;

in response to said indication message, said second peer performing a third local synchronization and generating a second peer change set;

said second peer leaving a second change set message on said way station peer;

appointing said first peer as an instigator a second time;

said first peer sending an indication to said second peer; and

determining that a prior synchronization attempt was made by using said way station module;

appointing said first peer as an instigator of another synchronization session a second time;

said first peer sending an indication to said second peer; and

determining that a prior synchronization attempt was made by using said way station peer.

27. The method of claim 26, comprising the additional step synchronizing using data from said second peer change set but without the involvement of said way station peer.

28. A media device readable by a computing apparatus and encoded with instructions stored thereon to cause the computing apparatus to perform a method of synchronizing a first peer with a second peer and a third peer, the method comprising the steps of:

appointing said first peer as an instigator of a synchronization session;

said first peer making an indication to said second and third peers;

in response to said indications, said second and third peers performing first local synchronizations and generating respectively a second peer change set and a third peer change set;

transmitting said second peer change set from said second peer to said first peer;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said second and third peer change sets from the second and third peers;

performing a second local synchronization at the first peer using the second and third peer change sets;

in response to said second local synchronization, said first peer producing a first return change set for said second peer and a second return change set for said third peer; and

said second peer and said third peer each performing a third local synchronization respectively using said first return change set and said second return change set.

29. The device of claim 28, wherein said first peer discovers a new peer through synchronization with said second peer.

30. The device of claim 28, wherein said first peer discovers a new peer through interaction with a way station software module.

31. The device of claim 30, wherein said first peer communicates with the way station software module to obtain information regarding the new peer.

32. The device of claim 31, wherein said way station software module runs on a hardware platform different from said first peer.

33. The device of claim 31, wherein said way station software module is associated with a directory data structure, said directory data structure comprising information regarding said sync system peers.

34. The device of claim 33, wherein said directory data structure comprises information regarding users of peer systems.

35. The device of claim 33, wherein said directory data structure comprises information regarding software or hardware platforms of said peer systems.

36. The device of claim 28, wherein said first peer presents a user interface to a user regarding the discovery of a new peer.

37. The device of claim 36, wherein said user interface regarding the discovery of the new peer system accepts input from a touch sensing system.

38. The device of claim of 37, wherein said accepted input comprises at least one gesture involving multiple simultaneous points of contact with the touch sensing system.

39. The device of claim of claim 37, wherein said user interface regarding the discovery of the new peer system accepts fusion input, said fusion input comprising input from a touch sensing system combined with at least one other type of input.

40. The device of claim 28, wherein said first peer uses Bonjour techniques to discover a new peer.

41. The device of claim 28, wherein said first peer uses Gnutella-type techniques to discover a new peer.

42. The device of claim 28, wherein said second peer and said third peer do not propagate additional change sets in response to performing the second local synchronization respectively using said first return change set and said second return change set.

43. The device of claim 28, wherein the step of transmitting said second peer change is preceded by the additional step of storing said second peer change set.

44. The device of claim 28, wherein the step of appointing said first peer as an instigator comprises the substeps of:

said first peer and said second peer both essentially simultaneously attempting to instigate a synchronization session;

said first peer learning about the activity of said second peer;

said first peer ceasing its instigating activity; and

said first peer, after ceasing its instigating activity, waiting a time period and after said time period, instigating a subsequent synchronization session.

45. The device of claim 44, wherein said time period is derived from a randomly determined data.

46. The device of claim 28, wherein said step of receiving said second and third change sets comprises the step of using NAT traversal techniques.

47. The device of claim 28, wherein said step of receiving said second and third peer change sets comprises the additional step of sending receipt acknowledgement indications respectively to said second peer and said third peer.

48. The device of claim 28, wherein:

the step of transmitting said second peer change is preceded by the additional step of storing said second peer change set;

said step of receiving said second peer change set comprises the additional step of sending receipt acknowledgement indications to said second peer; and

said second peer receiving said acknowledgement indication and in response thereto deleting said second peer change set.

49. A media device readable by a computing apparatus and encoded with instructions stored thereon to cause the computing apparatus to perform a method of synchronizing a first peer with a second peer and a third peer, wherein said second peer and said first peer communicate only by leaving messages with a way station peer, the method comprising the steps of:

appointing said first peer as an instigator for a synchronization session;

said first peer making an indication to said third peer;

said first peer leaving an indication message for said second peer on said way station peer;

in response said indication, said third peer performing a first local synchronization and generating a third peer change set;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said third peer change set and using said third peer change set to perform a second local synchronization;

after said second local synchronization, said second peer receiving said indication message via said way station peer;

in response to said indication message, said second peer performing a third local synchronization and generating a second peer change set; and

said first peer performing a fourth local synchronization using said second peer change set.

50. The device of claim 49, comprising the additional step of said second peer leaving a second change set message on said way station peer.

51. The device of claim 50, comprising the additional step of said first peer receiving said second change set message and then communicating directly with said second peer to acquire said second peer change set.

52. The device of claim 49, wherein said second change set message comprises said second peer change set.

53. A media device readable by a computing apparatus and encoded with instructions stored thereon to cause the computing apparatus to perform a method of synchronizing a first peer with a second peer and a third peer, wherein said second peer and said first peer communicate by leaving messages with a way station peer, the method comprising the steps of:

appointing said first peer as an instigator for a synchronization session;

said first peer making an indication to said third peer;

said first peer leaving an indication message for said second peer on said way station peer;

in response said indication, said third peer performing a first local synchronization and generating a third peer change set;

transmitting said third peer change set from said third peer to said first peer;

said first peer receiving said third peer change set and using said third peer change set to perform a second local synchronization;

after said second local synchronization, said second peer receiving said indication message via said way station peer;

in response to said indication message, said second peer performing a third local synchronization and generating a second peer change set;

said second peer leaving a second change set message on said way station peer;

appointing said first peer as an instigator a second time;

said first peer sending an indication to said second peer; and

determining that a prior synchronization attempt was made by using said way station module;

appointing said first peer as an instigator of another synchronization session a second time;

said first peer sending an indication to said second peer; and

determining that a prior synchronization attempt was made by using said way station peer.

54. The device of claim 53, comprising the additional step synchronizing using data from said second peer change set but without the involvement of said way station peer.