Method and apparatus for prioritizing data change requests and maintaining data consistency in a distributed computer system equipped for activity-based collaboration

• US 6,859,821 B1
• Filed: 07/19/1999
• Issued: 02/22/2005
• Est. Priority Date: 07/19/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Groove Networks, Inc. (Microsoft Corporation)
• Inventors: Ozzie, Jack E., Ozzie, Raymond E.
• Primary Examiner(s): Jean, Frantz B.
• Assistant Examiner(s): Choudhary, Anita
• Application Number:
  US09/356,148
• Time in Patent Office: 2,045 Days
• Field of Search: 707/201, 707/202, 707/203, 709/201, 709/205, 709/213, 709/204, 709/203, 709/248, 709/249, 715/511
• 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

A distributed, activity-based collaboration system can employ a data change request priority scheme for determining an order of execution of data change requests in effecting changes to local copies of data so as to optimize data consistency for collaborative activities. The data change request priority scheme can entail encoding sequence number information and dependency information in the data change requests, responsive to which data changes can be made, unmade and remade to the data.

Claims

1. A local network-capable device adapted for collaborative operation and communication over a network with at least one remote network-capable device to enable the local network-capable device and the remote network-capable device to cooperatively edit the same data, each of said local network-capable and remote network capable devices comprising:

A) a memory for storing a local copy of the data in accordance with a data model;

B) a data-change engine coupled with the memory, and responsive to a plurality of data change requests that have an absolute order relative to each other, for controlling storage of the local copy of data in the memory in accordance with the data model and making changes to the local copy of the data;

the data change requests including a locally-generated data change request and a remotely-generated data change request; and

C) a dynamics manager, coupled with the data-change engine, and responsive to the data change requests for controlling the engine and coordinating execution of the data change requests;

wherein the dynamics manager, responsive to the data change requests, can cause the making of received data changes in the absolute order, and, responsive to a data change request being received out of the absolute order, the undoing of the selected data changes to a point where a data change corresponding to the out-of-order data change request should have been made, the making the out-of-order change and the remaking of the undone data changes in the absolute order so that the same data changes are made in the same order to the local copies of the data stored in both the local network-capable device and the remote network-capable device.

2. The local network-capable device in accordance with claim 1, wherein the dynamics manager causes making, undoing and remaking of data changes in response to a data change request priority scheme.

3. The local network-capable device in accordance with claim 1, wherein the data change request priority scheme includes encoding the data change requests with request sequence numbers that define an absolute order of data change requests relative to each other, and the dynamics manager is responsive to the request sequence numbers in determining an order for making data changes specified by the data change requests.

4. The local network-capable device in accordance with claim 3, wherein the data change request priority scheme includes encoding the data change requests with an identifier corresponding to a characteristic of the network-capable device that generated the request, and the dynamics manager is responsive to the identifier in causing making of data changes.

5. The local network-capable device in accordance with claim 4, wherein each network capable device and a user thereof corresponds to an endpoint, and the identifier comprises an endpoint number corresponding to the endpoint that originated the data change request.

6. The local network-capable device in accordance with claim 5, wherein the request sequence numbers comprise endpoint relative sequence numbers, and the dynamics manager causes the data change requests to be processed in an order dependent on the endpoint relative sequence numbers and the endpoint numbers.

7. The local network-capable device in accordance with claim 3, wherein the data change request priority scheme includes a dependency identifier in each data change request, and the dynamics manager is responsive to the dependency identifier in causing undoing and remaking of data changes.

8. The local network-capable device in accordance with claim 7, wherein the dependency identifier specifies at least one data change request on which the encoded data change request depends.

9. The local network-capable device in accordance with claim 8, wherein the dependency identifier specifies one data change request on which encoded data change request depends.

10. The local network-capable device in accordance with claim 8, wherein the dynamics manager executes do, undo and redo operations with respect to data change requests to ensure that each one of the data change requests is processed only after the specified data change request on which the one data change request depends has been processed.

11. The local network-capable device in accordance with claim 8, wherein

A) the request sequence numbers comprise endpoint relative sequence numbers;

B) the dynamics manager causes the data change requests to be processed in an order dependent on the endpoint relative sequence numbers and the endpoint numbers; and

C) the dynamics manager causes data changes to be undone and remade responsive to the dependency identifier.

12. A distributed, coordinated system for maintaining plural copies of the same data pursuant to a distributed data model, wherein the copies can be changed responsive to users'"'"' actions, the system comprising:

A) a plurality of computer systems, each of the computer systems capable of locally generating a plurality of data change requests that have an absolute order relative to each other for changing a local copy of the data and of executing data change requests including the locally-generated data change requests and remotely-generated data change requests generated by others of the computer systems so as to make the requested changes to the local copy of the data;

B) each of the computer systems including a dynamics manager that receives locally-generated data change requests and remotely-generated data change requests for determining, responsive to information contained in the locally-generated and remotely-generated data change requests, the absolute order in which requested changes must be made to the local copy of the data, for making requested data changes in the determined order, for undoing data changes made when a remotely-generated data change request is received out of the determined order to the point where a data change corresponding to the out-of-order data change request can be made in the determined order and for remaking undone data changes in the absolute order.

13. The system in accordance with claim 12, wherein the dynamics manager of each computer system is responsive to data dependency information and request sequence information recorded in the data change requests in determining the absolute order in which the requested changes must be made to the local copy of the data;

the data dependency information comprising an indication of at least one prior data change request on which the data change request depends; and

the request sequence information indicating a sequential position of the data change request among a plurality of data change requests generated by the computer system that generated the data change request.

14. A framework apparatus for providing communication services for an activity-based collaboration system in which data change requests comprising deltas are communicated over a network between network-capable devices in order to maintain consistency between local data copies, each delta containing dependency information that absolutely orders that delta relative to all other deltas, the framework apparatus comprising a communications manager operable on a local network capable device for sending locally-generated deltas over a network to at least one remote network-capable devices and for receiving remotely-generated deltas from the at least one remote network-capable device;

and a dynamics manager responsive to the dependency information contained in the deltas for determining an order for processing the deltas to make changes to each local data copy, the dynamics manager being responsive to the reception of a remotely-generated delta out of the determined order for causing the selective undoing of changes made to a local data copy, the making of a data change corresponding to the out-of-order delta and the selective remaking of the undone data changes in the determined order.

15. A method for providing communication services for an activity-based collaboration system, in which data change requests comprising deltas are communicated over a network between network-capable devices in order to maintain consistency between local data copies, each delta containing sequence information that absolutely orders that delta relative to all other deltas, the method comprising the steps of:

A) sending locally-generated deltas from a local network-capable device over a network to at least one remote network-capable devices and for receiving remotely-generated deltas from the at least one remote network capable device;

B) determining an absolute order for processing the deltas based on sequence information contained within the deltas;

C) processing the deltas in the determined order thereby making changes to a local data copy as requested by the deltas;

D) undoing requested changes made to the local data copy in response to sequence information contained within the deltas indicating that a remotely-generated delta has been received out of the determined order;

E) making a data change to the local data copy corresponding to the out-of-order delta; and

F) remaking the undone data changes in the determined order.

16. A method for processing data change requests in a network-capable device having a local data copy and data change means for generating data change requests, each data change request containing information that absolutely orders that data chance request relative to all other data change requests, and specifying a change to be made to the local data copy, wherein the network-capable device communicates over a network with at least two other network-capable devices to enable all network-capable devices to cooperatively edit the same data during an editing session, the method comprising:

(a) when a first and second received data change requests require that a third data change have previously been made to the local data copy, determining the absolute order of making the data changes as specified by the first and second data change requests based on information contained in the data change requests;

(b) when a change specified by one of the first and second data change requests cannot be made in the order determined by the data change requests because other changes have already been made to the local data copy, undoing the other changes to the local data copy;

(c) making a change to the local data copy as specified by the one data change request; and

(d) redoing data changes undone in step (b) so that data changes are made to the local data copy consistently with changes made to local data copies in all network-capable devices.

17. The method of claim 16 wherein step (a) comprises:

(a1) when a first and second received data change requests require that a third data change have previously been made to the local data copy and the third change has not been made, placing the first and second received data change requests in a holding queue for subsequent processing.

18. The method of claim 17 wherein step (b) comprises:

(b1) when the changes specified by the first and second data change requests can be made in the order determined by the data change requests making the data changes specified by the data change requests in the determined order.

19. The method of claim 18 further comprising:

(e) determining whether changes to the local data copy specified by data change requests in the holding queue can be made.

20. The method of claim 19 wherein the information in the data change requests comprises an order in which each of the network-capable devices joined the editing session.

21. The method of claim 16 wherein the information in the data change requests further comprises a sequence number for each network-capable device.

22. The method of claim 16 further comprising:

(e) placing information for each change made to the local data copy in a data change log; and

(f) using the information in the data change log to undo changes to the local data copy.

23. The method of claim 22 further comprising:

(g) after each data change has been made, updating a timestamp vector comprising a data change sequence number for each endpoint.

24. The method of claim 23 wherein step (a) comprises:

(a2) when a first and second received data change requests require that a third data change have previously been made to the local data copy, using the timestamp vector to determine whether the third change has been made.

25. Apparatus for processing data change requests in a network-capable device having a local data copy and data change means for generating data change requests, each data change request containing information that absolutely orders that data change request relative to all other data change requests, and specifying a change to be made to the local data copy, wherein the network-capable device communicates over a network with at least two other network-capable devices to enable all network-capable devices to cooperatively edit the same data during an editing session, the apparatus comprising:

when a first and second received data change requests require that a third data change have previously been made to the local data copy, means for determining the absolute order of making the data changes as specified by the first and second data change requests based on information contained in the data change requests;

when a change specified by one of the first and second data change requests cannot be made in the order determined by the data change requests because other changes have already been made to the local data copy, means for undoing the other changes to the local data copy;

means for making a change to the local data copy as specified by the one data change request; and

means for redoing undone data changes so that data changes are made to the local data copy consistently with changes made to local data copies in all network-capable devices.

26. The apparatus of claim 25 wherein the means for determining an order of making the data changes comprises:

a holding queue; and

means operable when a first and second received data change requests require that a third data change have previously been made to the local data copy and the third change has not been made, for placing the first and second received data change requests in the holding queue for subsequent processing.

27. The apparatus of claim 26 further comprising means operable when the changes specified by the first and second data change requests can be made in the order determined by the data change requests for making the data changes specified by the data change requests in the determined order.

28. The apparatus of claim 27 further comprising means for determining whether changes to the local data copy specified by data change requests in the holding queue can be made.

29. The apparatus of claim 28 wherein the information in the data change requests comprises an order in which each of the network-capable devices joined the editing session.

30. The apparatus of claim 25 wherein the information in the data change requests further comprises a sequence number for each network-capable device.

31. The apparatus of claim 25 further comprising:

means for placing information for each change made to the local data copy in a data change log; and

mean for using the information in the data change log to undo changes to the local data copy.

32. The apparatus of claim 31 further comprising means operable after each data change has been made for updating a timestamp vector comprising a data change sequence number for each endpoint.

33. The apparatus of claim 32 wherein the means for determining an order of making the data changes comprises means operable when a first and second received data change requests require that a third data change have previously been made to the local data copy for using the timestamp vector to determine whether the third change has been made.