Method and system for resolving conflicts operations in a collaborative editing environment

• US 7,792,788 B2
• Filed: 03/04/2005
• Issued: 09/07/2010
• Est. Priority Date: 03/04/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Melmon, Keith, Nichols, David A.
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Nguyen; Loan T
• Application Number:
  US11/073,418
• Publication Number:
  US 20060200755A1
• Time in Patent Office: 2,013 Days
• Field of Search: None
• US Class Current: 707/608
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A collaborative editing system defines operational transforms for transforming conflicting operations on styles of the text of the document. The operational transforms ensure that local copies of the document will be consistent when it is in a quiescent state. The operational transforms are defined so that most conflicts can be resolved based on analysis of a remote operation and a local operation only. Certain conflicts, however, cannot be resolved based solely on analysis of the local and remote operations themselves. Such a conflict is referred to as a “definite conflict.” The collaborative editing system resolves definite conflicts by designating one of the computer systems as a distinguished computer system and giving priority to its operation. When a definite conflict arises, then the local computer system and the remote computer system recognize the conflict and resolve the conflict in favor of the operation of the distinguished computer system.

Claims

1. A method for transforming operations on an attribute of data, the data being updated by multiple devices having a local copy of the data, each of the multiple devices having a memory and a processor, the method comprising:

applying by a first device a first operation to a first copy of the data and sending an indication of the first operation to a second device, the first operation having a first operator and a first range, wherein the applying is performed by the processor of the first device executing instructions stored in the memory of the first device;

applying by the second device a second operation to a second copy of the data and sending an indication of the second operation to the first device, the second operation having a second operator and a second range, wherein the applying is performed by the processor of the second device executing instructions stored in the memory of the second device;

when the second device did not apply the first operation before applying the second operation, transforming by the first device the second operation to resolve any conflict with the first operation and applying the transformed second operation to the first copy of the data after the first operation has been applied, wherein the applying is performed by the processor of the first device executing instructions stored in the memory of the first device and further wherein when the first range and the second range overlap, transforming the second operation comprises adjusting a first end of the second range without adjusting a second end of the second range; and

when the first device did not apply the second operation before applying the first operation, transforming by the second device the first operation to resolve any conflict with the second operation and applying the transformed first operation to the second copy of the data after the second operation has been applied, wherein the applying is performed by the processor of the second device executing instructions stored in the memory of the second device and further wherein when the first range and the second range overlap, transforming the first operation comprises adjusting a first end of the first range without adjusting a second end of the first range,

wherein the transforming ensures that after applying the transformed operations the first copy and the second copy of the data are consistent.

2. The method of claim 1 wherein the first copy and the second copy are consistent when the first and second devices are in a quiescent state.

3. The method of claim 1 including when the first operation and the second operation indicate to change the same attribute and the first range and the second range are the same, the second operation is transformed by the first device to have no effect on the first copy and the first operation is not transformed by the second device.

4. The method of claim 1 including when the first operation and the second operation indicate to change the same attribute and the first range encapsulates the second range, the second operation is transformed by the first device to change the attribute in the same way as the first operation and the first operation is not transformed by the second device.

5. The method of claim 1 including when the first operation and the second operation indicate to change the same attribute and the first range and the second range overlap, the second operation is transformed by the first device by adjusting the range to remove the overlap and the first operation is not transformed by the second device.

6. The method of claim 1 including when the first operation indicates to replace and the second operation indicates to change an attribute and the first range encapsulates the second range, the second operation is transformed by the first device to have no effect.

7. The method of claim 1 including when the first operation indicates to replace and the second operation indicates to change an attribute and the second range encapsulates the first range, the second operation is transformed by the first device so that the end of the range is adjusted by the delta of the first operation and the first operation is transformed at the second device to have the attribute value of the second operation.

8. The method of claim 1 including when the first operation indicates to replace and the second operation indicates to change an attribute and the first range overlaps the second range and starts before the second range, the second operation is transformed by the first device so that the start of the second range is set to the end of the first range adjusted by the delta of the first range and the end of the second range is adjusted by the delta of the first range and the first operation is not transformed by the second device.

9. The method of claim 1 including when the first operation indicates to replace and the second operation indicates to change an attribute and the second range overlaps the first range and starts before the first range, the second operation is transformed by the first device by setting the end of the second range to the start of the first range and the first operation is not transformed by the second device.

10. A computer-readable storage medium containing instructions for controlling a first device to transform operations on the text style of text of a document, the document being updated by multiple devices in a collaborative editing environment, each device having a local copy of the document, by a method comprising:

applying a first operation to a first copy of the document maintained at the first device and sending an indication of the first operation to a second device, the first operation having a first operator and a first range;

receiving from the second device a message with an indication of a second operation that has been applied by the second device to a second copy of the document, the second operation having a second operator and a second range;

determining whether the received message indicates that the second device did not apply the first operation to the second copy of the document before applying the second operation to the second copy of the document;

upon determining that the second device did not apply the first operation to the second copy of the document before applying the second operation to the second copy of the document, transforming the second operation to resolve any definite conflict with the first operation in favor of a distinguished device and applying the transformed second operation to the first copy of the document after the first operation has been applied to the first copy of the document wherein

when the first operation and the second operation are to change the same style type of text and the first range overlaps the second range but does not encapsulate the second range,

when the first range starts before the second range, and the first device is the distinguished device, transforming the second operation by setting the start of the second range to the end of the first range without adjusting the end of the second range, and

when the first range starts after the second range, and the first device is the distinguished device, transforming the second operation by setting the end of the second range to the start of the first range;

when the first operation and the second operation are to change the same style type of text, the first range overlaps the second range but does not encapsulate the second range, and the second device is the distinguished device, not transforming the second operation; and

when the first operation and the second operation are to change the same style type of text and the first range encapsulates the second range, transforming the second operation by setting its attribute to the attribute of the first operation

wherein the transforming ensures that after applying the operations the first copy and the second copy of the data are consistent when the first and second devices are in a quiescent state and wherein at least one of the first operator and the second operator relate to changing the style of text of the document.

11. The computer-readable storage medium of claim 10 wherein the distinguished device is a server and the devices are clients.

12. The computer-readable storage medium of claim 10 wherein the distinguished device is a designated peer and the devices are peers.

13. The computer-readable storage medium of claim 10 wherein the distinguished device is the second device.

14. A computer system having a memory and a processor for transforming operations on an attribute of data, the data being updated by multiple devices having a local copy of the data, comprising:

a component that applies a local operation to the local copy of the data, the local operation having a local operator and a local range;

a component that receives an indication of a remote operation that has been applied by a device to a remote copy of the data, the remote operation having a remote operator and a remote range;

a component that determines which of the multiple devices is a distinguished device based at least in part on a network address of each device; and

a component that, when the remote device did not apply the local operation before applying the remote operation and the local operator and the remote operator are for adjusting the attribute of the data, transforms the remote operation to resolve any definite conflict with the local operation in favor of a distinguished device and applies the transformed remote operation to the local copy of the data after the local operation has been applied

wherein the components are stored as instructions in the memory for execution by the processor.

15. The computer system of claim 14 wherein the transforming of the remote operation does not split the remote operation into two operations.

16. The computer system of claim 14 wherein the component that determines which of the multiple devices is a distinguished device based at least in part on the network address of each device determines that the device with the highest network address is the determined device.

17. The computer system of claim 14 wherein the component that determines which of the multiple devices is a distinguished device based at least in part on the network address of each device determines that the device with the lowest network address is the determined device.