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

• US 20060200755A1
• Filed: 03/04/2005
• Published: 09/07/2006
• Est. Priority Date: 03/04/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nichols, David A., Melmon, Keith
• Granted Patent: US 7,792,788 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• 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, the method comprising:

applying at a first device a first operation to a first copy of the data and sending the first operation to a second device, the first operation having a first operator and a first range;

applying at the second device a second operation to a second copy of the data and sending the second operation to the first device, the second operation having a second operator and a second range;

when the second device did not apply the first operation before applying the second operation, transforming at 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; and

when the first device did not apply the second operation before applying the first operation, transforming at 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 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 at the first device to have no effect on the first copy and the first operation is not transformed at 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 at the first device to change the attribute in the same way as the first operation and the first operation is not transformed at 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 at the first device by adjusting the range to remove the overlap and the first operation is not transformed at 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 at 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 at 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 at 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 at 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 at 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 at the second device.

10. A computer-readable medium containing instructions for controlling a first device to transform operations on an attribute of data, the data being updated by multiple devices having a local copy of the data, by a method comprising:

applying a first operation to a first copy of the data and sending the first operation to a second device, the first operation having a first operator and a first range;

receiving a second operation that has been applied by the second device to a second copy of the data, the second operation having a second operator and a second range; and

when the second device did not apply the first operation before applying the second operation, 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 data after the first operation has been applied

wherein the transforming ensures that after applying the operations the first copy and the second copy of the data are consistent and wherein at least one of the first operator and the second operator relate to changing an attribute of data.

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

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

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

14. The computer-readable medium of claim 10 wherein the data is text and the attribute is text style.

15. The computer-readable medium of claim 14 wherein 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 it and starts before the second range, and the first device is the distinguished device, the second operation is transformed by setting the start of the second range to the end of the first range.

16. The computer-readable medium of claim 14 wherein 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 it and starts after the second range, and the first device is the distinguished device, the second operation is transformed by setting the end of the second range to the start of the first range.

17. The computer-readable medium of claim 14 wherein 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 it, and the second device is the distinguished device, the second operation is not transformed.

18. The computer-readable medium of claim 14 wherein 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, the second operation is transformed by setting its attribute to the attribute of the first operation.

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

means for applying a local operation to the local copy of the data, the local operation having a local operator and a local range;

means for receiving 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; and

means for, 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, transforming the remote operation to resolve any definite conflict with the local operation in favor of a distinguished device and applying the transformed remote operation to the local copy of the data after the local operation has been applied.

20. The computer system of claim 19 wherein the transforming of the remote operation does not split it into two operations.