Method and apparatus for designating endpoints in a collaborative computer system to facilitate maintaining data consistency

• US 8,024,404 B2
• Filed: 07/30/2003
• Issued: 09/20/2011
• Est. Priority Date: 07/19/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ozzie, Jack E., Ozzie, Raymond E.
• Primary Examiner(s): Zele; Krista
• Assistant Examiner(s): SCOTT, RANDY A
• Application Number:
  US10/630,472
• Publication Number:
  US 20040024820A1
• Time in Patent Office: 2,974 Days
• Field of Search: 709/205, 709/227, 709/233, 709/463, 709/42, 463/42
• US Class Current: 709/205
• CPC Class Codes: G06F 16/1767 Concurrency control, e.g. optimistic or pessimistic approaches
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 51/043 using or handling presence information
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

In a peer-to-peer collaborative system in which collaborators communicate via a shared telespace and exchange data change requests, a unique number is assigned to each endpoint (a unique pairing of a device and a person) of each of the telespace members. Each endpoint number indicates the order in which the member joined the telespace, and, for each member invited to join (or otherwise sponsored) by another telespace member (the “inviting member”), it also indicates the inviting member. As more and more members are invited to join by those new members, the designations add additional orders of digits to indicate the family tree or chain of inviting members. The designations are used to resolve collisions between two data change requests that are both dependent on the same data change request.

Claims

1. A method of operating a plurality of computers to implement a distributed method for assigning designations to endpoints for use in a peer-to-peer collaboration system having a plurality of members that share a telespace and exchange data change requests, the method comprising:

operating each of at least two of the plurality of computers in the peer-to-peer collaboration system to perform acts comprising;

inviting an invited member to join the telespace;

independently assigning a unique designation to an endpoint of the member invited to join the telespace, each designation of an endpoint of the invited member comprising;

(a) a value indicative of the order in which the invited member was invited by a respective inviting member to join the telespace; and

(b) a unique endpoint designation indicative of the respective inviting member; and

ordering received data change messages based on endpoint designations in the received data change messages.

2. The method of claim 1 wherein (a) comprises a unique numeral designation for each endpoint.

3. The method of claim 2 wherein (b) comprises a unique serial numeral designation for each endpoint, wherein the serial numeral designation comprises a series of numbers including the numeral designation of the respective inviting member.

4. The method of claim 1, wherein a plurality of the designations of different endpoints each indicate a chain of inviting members.

5. The method of claim 1, wherein endpoint designations comprise a number of orders, including a first order designating a founding member of the telespace, and at least a second order designating a member invited to join the telespace by the founding member.

6. The method of claim 1,

wherein the method comprises:

upon creation of the telespace, an endpoint corresponding to a founding telespace member assigning itself a unique designation comprising a first order digit; and

subsequent to creation of the telespace, assigning, by the founding member, each of a plurality of endpoints corresponding to a new member of the telespace invited into the telespace by the founding member a unique designation comprising the first order digit of the founding telespace member, and a second order digit, the second order digits of the designations of endpoints of the new members being in a sequential order indicating the order in which the new members joined the telespace.

7. The method of claim 6 further comprising:

inserting endpoint designations into data change requests.

8. The method of claim 7 further comprising:

using the endpoint designations in data change requests to resolve a dependency collision between two data requests.

9. The method of claim 8 wherein using the end point designations in data change requests to resolve a dependency collision comprises resolving a dependency collision while maintaining total ordering.

10. The method of claim 9 wherein using the end point designations in data change requests to resolve a dependency collision comprises:

comparing endpoint digits on an order-by-order basis; and

scheduling data change requests so that data change requests with the lowest endpoint digits in the lowest orders are scheduled for processing first.

11. The method of claim 1 further comprising:

inserting endpoint designations into data change requests.

12. The method of claim 11 further comprising:

using the endpoint designations in data change requests to resolve a dependency collision between two data requests.

13. The method of claim 12 wherein using the end point designations in data change requests to resolve a dependency collision comprises resolving a dependency collision while maintaining total ordering.

14. The method of claim 1 wherein each unique endpoint designation is unique within the telespace.

15. The method of claim 1, wherein each unique endpoint designation is unique within the collaboration system.

16. A distributed apparatus for assigning designations to endpoints for use in a peer-to-peer collaboration system having a plurality of members that share a telespace and exchange data change requests, the apparatus comprising:

means for forming the telespace by inviting members to join the telespace;

means for assigning a unique designation to each endpoint of each member of the telespace, each designation of a member comprising a portion indicative of the order in which the member joined the telespace and a portion indicative of an inviting member inviting the member to join the telespace, the means for assigning comprising means operable by each of the inviting members for assigning a unique designation to each new telespace member that an inviting endpoint invites into the telespace; and

means for resolving dependency collisions between a plurality of data change messages, the dependency collisions being resolved based on respective unique designations in each of the plurality of data change messages, the unique designations being assigned by the means for assigning.

17. The apparatus of claim 16 wherein the means for assigning endpoint designations for each member comprises means for assigning a unique numeral designation to each endpoint.

18. The apparatus of claim 17 wherein the means for assigning the unique designation comprises means for assigning a unique serial numeral designation to each endpoint wherein the serial numeral designation comprises a series of numbers including the numeral designation of the inviting member.

19. The apparatus of claim 16, wherein a plurality of the designations of different endpoints each indicate a chain of inviting members.

20. The apparatus of claim 16, wherein the unique designations comprise a number of orders, including a first order designating a founding member of the telespace, and at least a second order designating a member invited to join the telespace by the founding member.

21. The apparatus of claim 16, wherein the means for assigning the unique designation comprises:

means operable upon creation of the telespace, for assigning to an endpoint corresponding to a founding telespace member a unique designation comprising a first order digit; and

wherein the means for assigning invited member endpoint designations comprises;

means operable subsequent to creation of the telespace and by the founding member, for assigning each of a plurality of endpoints corresponding to a new member of the telespace invited into the telespace by the founding member a unique designation comprising the first order digit of the founding telespace member, and a second order digit, the second order digits of the designations of endpoints of the new members being in a sequential order indicating the order in which the new members joined the telespace.

22. The apparatus of claim 21 further comprising means for inserting endpoint designations into data change requests.

23. The apparatus of claim 22, wherein the means for resolving a dependency collision comprises means for resolving a dependency collision while maintaining total ordering.

24. The apparatus of claim 23 wherein the means for resolving a dependency collision comprises:

means for comparing endpoint digits on an order-by-order basis; and

means scheduling data change requests so that data change requests with the lowest endpoint digits in the lowest orders are scheduled for processing first.

25. The apparatus of claim 16 further comprising means for inserting endpoint designations into data change requests.

26. The apparatus of claim 25, wherein the means for resolving a dependency collision comprises means for resolving a dependency collision while maintaining total ordering of the data change requests in each of a plurality of endpoints.

27. The apparatus of claim 16 wherein the means operable by each of the inviting members for assigning the unique designation comprises, for each member invited to join the telespace by another telespace member, means in the inviting member for assigning a endpoint designation that is unique within the telespace.

28. The apparatus of claim 16, wherein the means operable by each of the inviting members for assigning the unique designation comprises, for each member invited to join the telespace by another telespace member, means operable by the inviting member for assigning a endpoint designation that is unique within the collaboration system.

29. The apparatus of claim 16, wherein the means for assigning the unique designation comprises a pseudo-random number generator that generates each designation.

30. Computer readable storage comprising computer-executable instructions that, when executed by a processor, perform a method of operating a computer of an invited member of a peer-to-peer collaboration system in which computers used by a plurality of members communicate changes to a shared telespace by transmitting change messages and the computers used by the plurality of members maintain a copy of the shared telespace by applying changes in the change messages, the method comprising:

receiving an invitation for the invited member to join the shared telespace, the invitation being sent by an inviting member of the plurality of members having an inviting member endpoint designation;

receiving from a computer of the inviting member of the peer-to-peer collaboration system an invited member endpoint designation for the invited member, the invited member endpoint designation having a hierarchical representation with a first portion identifying the inviting member endpoint designation and a second portion identifying when the invited member was invited to join the shared telespace relative to when the inviting member invited other members to join the shared telespace; and

transmitting change messages indicating changes to the shared telespace, each change message comprising the invited member endpoint designation.

31. The computer-readable storage of claim 30, wherein the second portion of the invited member endpoint designation comprises a sequence number generated by the inviting member.

32. The computer-readable storage of claim 30, wherein the method further comprises:

inviting a second invited member to join the telespace; and

providing to a computer of the second invited member a second invited member designation, the second invited member designation having a hierarchical representation comprising;

a first portion identifying the inviting member endpoint designation;

a second portion identifying when the invited member was invited to join the shared telespace relative to when the inviting member invited other members to join the telespace; and

a third portion identifying when the second invited member was invited to join the shared telespace relative to when the invited member invited other members to join the telespace.