Method, system, and apparatus for enabling near real time collaboration on an electronic document through a plurality of computer systems

• US 20050234943A1
• Filed: 08/18/2004
• Published: 10/20/2005
• Est. Priority Date: 04/20/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Clarke, Simon Peter
• Granted Patent: US 7,818,679 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 67/131 Protocols for games, networked simulations or virtual reality

Abstract

A method, system, and apparatus are provided for collaborating on an electronic document. According to the method, a data structure may be maintained at each of the computer systems participating in the collaborative session that represents the contents of a shared document. When user input is received at one of the computer systems modifying the document, the data structure is updated to reflect the modification. In response to the modification, the changes to the data structure are periodically identified and collected as a revision that identifies only the changes made to the data structure as a result of the edits made since the previous revision was taken. The revision is packaged and transmitted to each of the participants in the sharing session. The revisions are merged into the copy of the data structure stored at the participating computer systems.

Claims

1. A method for enabling near real time collaboration on an electronic document through a plurality of computer systems, the method comprising:

maintaining a data structure representing the entire contents of the electronic document;

receiving user input at a first of the plurality of computer systems, the user input comprising a modification to the data structure;

in response to the modification of the data structure, creating a revision that identifies only the modification to the data structure; and

transmitting the revision to each of the plurality of computer systems other than the computer system at which the input was made.

2. The method of claim 1, further comprising:

receiving the revision at a second of the plurality of computer systems;

merging the revision into a version of the data structure maintained at the second of the plurality of computer systems; and

displaying the contents of the data structure at the second of the plurality of computer systems.

3. The method of claim 2, further comprising prior to transmitting the revision:

determining at the first computer system whether the data structure is current; and

if the data structure is not current, retrieving and merging the necessary revisions to make the data structure current.

4. The method of claim 3, further comprising prior to transmitting the revision:

determining at the first computer system whether the first computer system is the owner of a synchronization token;

in response to determining that the first computer system is not the owner of the synchronization token, requesting the synchronization token from the owner of the synchronization token; and

in response to determining that the first computer system is the owner of the synchronization token, transmitting the revision to each of the plurality of computer systems other than the computer system at which the input was made.

5. The method of claim 4, wherein requesting the synchronization token from the owner of the synchronization token comprises:

generating a request for the synchronization token, the request including data indicating the duration of time the first computer system has been waiting for the synchronization token;

transmitting the request to the computer system owning the synchronization token;

determining whether the synchronization token has been received;

in response to determining that the synchronization token has not been received, generating a new request for the synchronization token, the new request including data indicating the extended duration of time the first computer has been waiting for the synchronization token; and

transmitting the new request to the computer system owning the synchronization token.

6. The method of claim 5, further comprising:

receiving the synchronization token;

determining whether two synchronization tokens exist; and

in response to determining that two synchronization tokens exist, performing a calculation to determine which of the two synchronization tokens should be deleted.

7. The method of claim 5, further comprising:

receiving a request for the synchronization token;

in response to the request, determining whether the synchronization token has been previously transmitted to a one of the plurality of computer systems;

if the synchronization token has not been previously transmitted, identifying the request for the synchronization token having the longest time spent waiting for the synchronization token; and

transmitting the synchronization token to the computer system that transmitted the request for the synchronization token having the longest time spent waiting.

8. The method of claim 7, further comprising:

if the synchronization token has been previously transmitted,

decreasing a time to live value in the request for the synchronization token,

determining whether the time to live value is greater than zero, and

if the time to live value is greater than zero, forwarding the request to the current owner of the synchronization token.

9. The method of claim 8, wherein the data structure comprises a direct acyclic graph.

10. A computer-readable medium having computer-executable instructions stored thereon which, when executed by a computer, will cause the computer to perform the method of claim 1.

11. A computer-controlled apparatus capable of performing the method of claim 1.

12. A method for enabling near real time collaboration on a page of an electronic document through a plurality of computer systems, the method comprising:

maintaining a graph at each of the computer systems, the connected graph identifying the contents of the page of the electronic document;

receiving at a first of the plurality of computer systems a change to the page, the change to the page resulting in a corresponding change to the graph;

generating a revision to the graph in response to the change, the revision comprising data identifying only the change to the graph;

transmitting the revision from the first of the plurality of computer systems to each of the other computer systems; and

merging the revision into the graph maintained at each of the other computer systems.

13. The method of claim 12, further comprising prior to transmitting the revision:

determining whether the first of the plurality of the computer systems is the owner of a synchronization token; and

transmitting the revision only if the first computer system is the owner of the synchronization token.

14. The method of claim 13, further comprising:

receiving at the first computer system one or more requests for the synchronization token from the other computers, each request specifying the amount of time the computer making the request has been waiting to receive the synchronization token;

in response to receiving one or more requests for the synchronization token, determining from the requests the computer that has been waiting the longest amount of time for the synchronization token; and

transmitting the synchronization token to the computer that has been waiting the longest amount of time.

15. The method of claim 14, further comprising in response to receiving one or more requests for the synchronization token:

determining whether the synchronization token has been previously forwarded; and

in response to determining that the synchronization token has been previously forwarded, decreasing a time to live value in each of the received requests for the synchronization token and forwarding the requests to the current owner of the synchronization token.

16. The method of claim 15, further comprising:

determining whether two synchronization tokens exist; and

in response to determining that two synchronization tokens exist, executing an identical algorithm at each of the computer systems owning a synchronization token to determine which of the two synchronization tokens should be deleted.

17. The method of claim 16, further comprising:

executing at each of the plurality of computers systems a page synchronization object operative to listen on a communications channel for revisions to the page, to receive revisions to the page, and to modify the graph when a revision has been received.

18. The method of claim 17, wherein the electronic document comprises multiple pages and wherein a synchronization object is created for each page.

19. A computer-readable medium having computer-executable instructions stored thereon which, when executed by a computer, will cause the computer to perform the method of claim 12.

20. A computer-controlled apparatus capable of performing the method of claim 12.