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

• US 7,818,679 B2
• Filed: 08/18/2004
• Issued: 10/19/2010
• 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
• Primary Examiner(s): Huynh; Ba
• Assistant Examiner(s): WIENER, ERIC A
• Application Number:
  US10/920,640
• Publication Number:
  US 20050234943A1
• Time in Patent Office: 2,253 Days
• Field of Search: 715751-759, 715/748, 370/437, 370/449, 709201-205, 709238-240, 709/245, 709/246, 719/311, 719/312, 719/329
• US Class Current: 715/751
• 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:

initiating a sharing session on a first computer system, wherein initiating the sharing session comprises;

creating a page synchronization object, and

creating channels to communicate with the first computer system;

accepting requests from at least a second computer system to join the sharing session;

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

receiving user input at one of the plurality of computer systems joined to the sharing session, the user input comprising a modification to the data structure;

adding, in response to the received user input, a new node representing the modification to the data structure;

in response to the modification to the data structure, creating a revision that identifies only the modification to the data structure, wherein creating the revision comprises;

periodically identifying changes to the data structure, and

periodically collecting the identified changes to the data structure as a result of the modification; and

transmitting the revision to each of the plurality of computer systems joined to the sharing session other than the one computer system at which the input was made, wherein transmitting the revision to each of the plurality of computer systems joined to the sharing session comprises;

determining whether a synchronization token is present,

serializing the revision,

placing a reference in the synchronization token,

sending the serialized revision and the synchronization token with the reference, wherein sending the serialized revision and the synchronization token with the reference comprises using a throttling mechanism associated with sending the serialized revision only to computer systems of the plurality of computer systems that have finished processing a previous revision of the data structure, and

applying the revision to a locally stored copy at each receiving computer system of the plurality of computer systems joined to the sharing session.

2. The method of claim 1, further comprising:

receiving the revision at another one of the plurality of computer systems not having inputted the modification;

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

displaying the contents of the data structure at the other one of the plurality of computer systems.

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

determining, at the one computer system providing the received user input, whether the data structure is current; and

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

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

determining, at the one computer system providing the received user input, whether the one computer system is an owner of the synchronization token;

in response to determining that the one 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 one computer system is the owner of the synchronization token, transmitting the revision to each of the plurality of computer systems joined to the sharing session other than the one 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 a duration of time the one computer system has been waiting for the synchronization token;

transmitting the request to a corresponding 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 an extended duration of time the one computer has been waiting for the synchronization token; and

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

6. The method of claim 5, further comprising:

receiving the synchronization token at the one computer system providing the received user input;

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 the request for the synchronization token at the corresponding computer system owning the synchronization token;

in response to the request, determining whether the synchronization token has been previously transmitted to any 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 duration of time waiting for the synchronization token; and

transmitting the synchronization token to a pending computer system that transmitted the request for the synchronization token having the longest duration of 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 a current owner of the synchronization token.

9. The method of claim 1, 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 executable storage apparatus capable of performing the method of claim 1.

17. The method of claim 1, 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 revisions have been received.

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

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:

initiating a sharing session on one of the plurality of computer systems;

accepting requests respectively from others of the plurality of computer systems to join the sharing session;

maintaining a graph at each of the computer systems joined to the sharing session, the graph identifying a content of the page of the electronic document;

receiving at a first of the plurality of computer systems joined to the sharing session 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, wherein generating the revision comprises;

periodically identifying changes to a data structure, and

periodically collecting the identified changes to the data structure as a result of the change to the graph;

transmitting the revision from the first of the plurality of computer systems to each of the other computer systems joined to the sharing session, wherein transmitting the revision to each of the plurality of computer systems joined to the sharing session comprises;

determining whether a synchronization token is present,

serializing the revision,

placing a reference in the synchronization token,

sending the serialized revision and the synchronization token with the reference, wherein sending the serialized revision and the synchronization token with the reference comprises using a throttling mechanism associated with sending the serialized revision only to computer systems of the plurality of computer systems that have finished processing a previous revision of the data structure, and

applying the revision to a locally stored copy at each receiving computer system of the plurality of computer systems joined to the sharing session, wherein applying the revision to a locally stored copy comprises;

determining whether at least one local change is present at a receiving computer system receiving the revision,

in response to determining whether at least one local change is present, determining whether the synchronization token is available at the receiving computer system of the plurality of computer systems,

in response to determining whether the synchronization token is available at the receiving computer system of the plurality of computer systems;

applying the at least one local change to the revision, and

transmitting the revision to others of the plurality of computer systems joined to the sharing session other than the computer system at which the at least one local change was made,

in response to determining whether the synchronization token is not available at the receiving computer system of the plurality of computer systems, merging the following;

a base line, wherein the baseline is the last version received,

the revision, and

the at least one local change; and

merging the revision into the graph maintained at each of the other computer systems joined to the sharing session; and

transmitting a current version of the data structure representing the entire contents of the electronic document to the others of the plurality of computer systems that joined the sharing session after the revision, wherein transmitting the current version of the data structure comprises;

creating a synchronization object for each new channel that has not previously received a request to join the sharing session,

creating a new page,

linking the new page to the synchronization object, and

transmitting the content of the electronic document on each new channel, wherein transmitting each content of the electronic document on each new channel comprises;

allowing users to edit different contents without at least one of the following;

conflicting edits and conflicting revisions, and

allowing users to edit the same content.

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 the 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 at least one request for the synchronization token from the other computers, each request specifying an amount of time the requesting computer system making the request has been waiting to receive the synchronization token;

in response to receiving the at least one request 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 the at least one request 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 a 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 any one of the two synchronization tokens to determine which of the two synchronization tokens should be deleted.

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 executable storage apparatus capable of performing the method of claim 12.