Method and apparatus for maintaining consistency of a shared space across multiple endpoints in a peer-to-peer collaborative computer system

• US 20070255787A1
• Filed: 06/22/2007
• Published: 11/01/2007
• Est. Priority Date: 10/24/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ozzie, Jack, Ozzie, Raymond, Richardson, Ransom
• Granted Patent: US 8,073,905 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

In a peer-to-peer collaboration system, deltas containing data change commands are organized in a persistent data structure called a delta log. The delta log is organized into blocks, which are the largest division in the delta log. In turn, blocks contain groups, groups contain chains and chains contain deltas. Delta blocks are used to implement priority deltas that are used to limit the collection of data change commands that must be transferred. Within a block the deltas are organized by groups, each of which is a set of deltas organized into chains. The delta group in used to determine which deltas to purge. The chains are ordered by increasing creator ID of the endpoint that created the chain. Organizing the delta log in this fashion allows the log to be “walked” to detect convergence problems. To achieve causality-preservation, each delta has a list of dependencies representing other deltas that must be executed before the current delta can be executed. The dynamics manager uses the ability to do (execute) and undo commands to perform roll back and roll forward operations on deltas in order to achieve convergence.

Claims

1-54. -54. (canceled)

55. Apparatus for maintaining consistency of a shared space across multiple endpoints in a collaborative computer system wherein each endpoint has a local data copy and endpoints transmit data change commands to each other in order to update the local data copies, the apparatus comprising:

a first tool in one endpoint that is responsive to user actions at the endpoint for creating a first delta container to transmit data change commands to other endpoints and for adding data change commands to the first delta container;

a second tool in the one endpoint that is called by the first tool to add data change commands to the first delta container; and

means in the second tool for creating a second delta container, adding the second delta container to the first delta container and adding data change commands to the second delta container.

56. The apparatus of claim 55 wherein at least one of the data change commands includes undo information for reversing the data change performed by the command.

57. The apparatus of claim 55 further comprising a data change engine for executing the data change commands in the first delta container and the data change commands in the second delta container and a dynamics manager for adding the data change commands in the second delta container and undo information corresponding to the data change commands in the second delta container to the beginning of the first delta container.

58. The apparatus of claim 57 wherein the data change engine executes data change commands added to the first delta container before the second delta container was added to the first delta container after the data change commands in the second delta container are executed and added.

59. The apparatus of claim 58 wherein the data change engine comprises means responsive to the occurrence of an error during the execution of the data change commands in the first delta container for aborting the execution of the data change commands in the second delta container.

64. The method of claim 58 further comprising:

(h) aborting the execution of the data change commands in the second delta container upon the occurrence of an error during the execution of the data change commands in the first delta container.

60. A method for maintaining consistency of a shared space across multiple endpoints in a collaborative computer system wherein each endpoint has a local data copy and endpoints transmit data change commands to each other in order to update the local data copies, the method comprising:

(a) using a first tool to create a first delta container in response to user actions at one endpoint to transmit data change commands to other endpoints;

(b) using the first tool to add data change commands to the first delta container;

(c) calling a second tool in the one endpoint with the first tool to add data change commands to the first delta container;

(d) creating a second delta container with the second tool; and

(e) using the second tool to add the second delta container to the first delta container and to add data change commands to the second delta container.

61. The method of claim 60 wherein at least one of the data change commands includes undo information for reversing the data change performed by the command.

62. The method of claim 60 further comprising:

executing the data change commands in the second delta container and the data change commands in the first delta container; and

after executing the data change commands in the second delta container, adding the data change commands in the second delta container and undo information corresponding to the data change commands in the second delta container to the beginning of the first delta container.

63. The method of claim 62 wherein step (f) comprises executing the data change commands added to the first delta container before the second delta container was added after step (g) is performed.

65. Apparatus for maintaining consistency of a shared space across multiple endpoints in a collaborative computer system wherein each endpoint has a local data copy and endpoints transmit data change commands contained in delta containers to each other in order to update the local data copies, the apparatus comprising:

a data change engine in one endpoint for executing the data change commands in a first delta container, for generating undo information in order to reverse the effects of the data change commands and for storing the undo information in the first data change container;

means in the data change engine and responsive to the execution of a selected data change command for creating a second delta container in the one endpoint and for adding data change commands to the second delta container.

66. The apparatus of claim 65 further comprising means for executing the commands in the second delta container and for generating undo information for reversing the effects of the commands in the second delta container and means operable upon execution for storing the commands in the second delta container and undo information generated for those commands in the undo information of the first delta container.

67. The apparatus of claim 66 further comprising means for using the undo information in the first delta container to reverse the effect of the commands contained in the first delta container wherein the means for using the undo information reverses commands originally stored in the second delta container before the selected command that caused the second delta container to be created is reversed.

68. A method for maintaining consistency of a shared space across multiple endpoints in a collaborative computer system wherein each endpoint has a local data copy and endpoints transmit data change commands contained in delta containers to each other in order to update the local data copies, the method comprising:

(a) executing the data change commands in a first delta container, generating undo information in order to reverse the effects of the data change commands and storing the undo information in the first data change container;

(b) responsive to the execution of a selected data change command, creating a second delta container in the one endpoint; and

(c) adding data change commands to the second delta container.

69. The method of claim 68 further comprising:

(d) executing the commands in the second delta container and generating undo information for reversing the effects of the commands in the second delta container; and

(e) storing the executed commands from the second delta container and undo information generated for those commands in the undo information of the first delta container.

70. The method of claim 69 further comprising:

(f) using the undo information in the first delta container to reverse the effect of the commands contained in the first delta container; and

(g) during the performance of step (f) reversing commands originally stored in the second delta container before the selected command that caused the second delta container to be created is reversed.

71-78. -78. (canceled)