Resolving update-delete conflicts

• US 20070282914A1
• Filed: 05/31/2006
• Published: 12/06/2007
• Est. Priority Date: 05/31/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sivapragasam, Muhunthan, Cao, Don, Hudis, Irena, Novik, Lev, Talius, Tomas, Jhaveri, Vivek J., Wu, Yunxin, Tang, Ann
• Granted Patent: US 7,769,727 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Update-delete conflicts detected during synchronization can be resolved in favor of the update or the deletion. Resolving the conflict in favor of the deletion results in the entity deleted on one replica being deleted on all selected replicas. Resolving the conflict in favor of the update results in the updated entity, which includes an entity moved from one hierarchy to another, being replicated on all selected replicas. To resolve the conflict in favor of the update, the deletion is treated as though it were reported erroneously. The deleted entity is resurrected in the form of the updated entity. Change version information is maintained in all replicas. Update-delete conflicts are resolvable in accordance with various resolution policies such as the update wins, deletion wins, changes occurring on a particular device wins, and most recent event wins, for example.

Claims

1. A method for resolving conflicts, the method comprising:

receiving an indication that an entity in a first replica was updated (12);

receiving an indication that the entity in a second replica was deleted (14);

receiving one of;

an indication that the deletion of the entity was erroneous; and

no indication that the deletion of the entity was erroneous;

if no indication is received that the deletion of the entity was erroneous, deleting the entity from the first replica and the second replica; and

if an indication is received that the deletion of the entity was erroneous;

requesting from the first replica the updated entity; and

replicating the updated entity in the first replica and the second replica.

2. A method in accordance with claim 1, wherein deleting comprises deleting all child entities in a hierarchy to which the deleted entity belongs.

3. A method in accordance with claim 1, wherein replicating the updated entity comprises replicating all child entities in a hierarchy to which the entity belongs.

4. A method in accordance with claim 1, further comprising performing one of the steps of replicating and deleting in accordance with a conflict resolution policy, wherein the conflict resolution policy comprises one of resolving a conflict in favor of an update, resolving a conflict in favor of a deletion, resolving a conflict in favor of a remote replica, resolving a conflict in favor of a local replica, and resolving a conflict in accordance with a most recent occurrence of the update or the deletion.

5. A method in accordance with claim 4, further comprising:

if the conflict resolution policy comprises resolving a conflict in favor of an update, performing the step of replicating;

if the conflict resolution policy comprises resolving a conflict in favor of a deletion;

performing the step of deleting;

if the conflict resolution policy comprises resolving a conflict in favor of a remote replica;

performing the step of deleting, if the first replica comprises the remote replica; and

performing the step of replicating, if the second replica comprises the remote replica;

if the conflict resolution policy comprises resolving a conflict in favor of a local replica;

performing the step of deleting, if the first replica comprises the local replica; and

performing the step of replicating, if the second replica comprises the local replica; and

if the conflict resolution policy comprises resolving a conflict in accordance with a most recent occurrence of the update or the deletion;

performing the step of deleting, if the deletion occurred more recently than the updated; and

performing the step of replicating, if the update occurred more recently than the deletion.

6. A method in accordance with claim 1, wherein replicating further comprises:

assigning a new change version to the deleted entity, wherein the new change version is based on the updated entity and comprises an indicator marking the deleted entity for resurrection; and

resurrecting the deleted entity to the updated entity.

7. A method in accordance with claim 1, further comprising:

determining if at least one child entity in a hierarchy to which the deleted entity belonged was deleted; and

if the at least one child entity was deleted, resurrecting the at least one child entity.

8. A method in accordance with claim 1, wherein the step of deleting further comprises:

determining if the deleted entity had at least one child entity in a hierarchy to which the deleted entity belonged; and

if the deleted entity had at least one child entity, deleting the entity and the at least one child entity.

9. A method in accordance with claim 1, wherein:

the update to the entity on the first replica comprises moving the entity from a first hierarchy to a second hierarchy in the first replica;

the deletion to the entity in the second replica comprises deletion the second hierarchy in the second replica;

replicating further comprises replicating the entity in the second hierarchy in the first replica and the second replica; and

deleting further comprises deleting the second hierarchy from the first replica and the second replica.

10. A system for resolving conflicts, the system comprising:

an input/output portion (98) for;

receiving an indication that an entity in a first replica was updated;

receiving an indication that the entity in a second replica was deleted;

receiving an indication that a deletion of an entity was erroneous; and

receiving no indication that the deletion of the entity was erroneous;

a processing portion (94) for;

if no indication is received that the deletion of the entity was erroneous, deleting the entity from the first replica and the second replica; and

if an indication is received that the deletion of the entity was erroneous;

requesting from the first replica the updated entity; and

replicating the updated entity in the first replica and the second replica; and

a memory portion (96) for storing information pertaining to updated and deleted entities.

11. A system in accordance with claim 10, the processing portion further for deleting all child entities in a hierarchy to which the deleted entity belongs.

12. A system in accordance with claim 10, the processing portion further for replicating the updated entity comprises replicating all child entities in a hierarchy to which the entity belongs.

13. A system in accordance with claim 10, the processing portion further for performing one of replicating and deleting in accordance with a conflict resolution policy, wherein the conflict resolution policy comprises one of resolving a conflict in favor of an update, resolving a conflict in favor of a deletion, resolving a conflict in favor of a remote replica, resolving a conflict in favor of a local replica, and resolving a conflict in accordance with a most recent occurrence of the update or the deletion.

14. A system in accordance with claim 13, the processing portion further for:

if the conflict resolution policy comprises resolving a conflict in favor of an update, performing the step of replicating;

if the conflict resolution policy comprises resolving a conflict in favor of a deletion;

performing the step of deleting;

if the conflict resolution policy comprises resolving a conflict in favor of a remote replica;

performing the step of deleting, if the first replica comprises the remote replica; and

performing the step of replicating, if the second replica comprises the remote replica;

if the conflict resolution policy comprises resolving a conflict in favor of a local replica;

performing the step of deleting, if the first replica comprises the local replica; and

performing the step of replicating, if the second replica comprises the local replica; and

if the conflict resolution policy comprises resolving a conflict in accordance with a most recent occurrence of the update or the deletion;

performing the step of deleting, if the deletion occurred more recently than the updated; and

performing the step of replicating, if the update occurred more recently than the deletion.

15. A system in accordance with claim 10, to accomplish replication, the processing portion further for:

assigning a new change version to the deleted entity, wherein the new change version is based on the updated entity and comprises an indicator marking the deleted entity for resurrection; and

resurrecting the deleted entity to the updated entity.

16. A system in accordance with claim 10, the processing portion further for:

determining if at least one child entity in a hierarchy to which the deleted entity belonged was deleted; and

if the at least one child entity was deleted, resurrecting the at least one child entity.

17. A system in accordance with claim 10, to accomplish deletion, the processing portion further for:

determining if the deleted entity had at least one child entity in a hierarchy to which the deleted entity belonged; and

if the deleted entity had at least one child entity, deleting the entity and the at least one child entity.

18. A system in accordance with claim 10, wherein:

the update to the entity on the first replica comprises moving the entity from a first hierarchy to a second hierarchy in the first replica;

the deletion to the entity in the second replica comprises deletion the second hierarchy in the second replica;

replicating further comprises replicating the entity in the second hierarchy in the first replica and the second replica; and

deleting further comprises deleting the second hierarchy from the first replica and the second replica.

19. A computer-readable medium having computer-executable instructions thereon for resolving conflicts, the computer-executable instructions for performing the steps of:

receiving an indication that an entity in a first replica was updated (12);

receiving an indication that the entity in a second replica was deleted (14);

receiving an indication that the deletion of the entity was erroneous; and

receiving no indication that the deletion of the entity was erroneous;

if no indication is received that the deletion of the entity was erroneous, deleting the entity from the first replica and the second replica; and

deleting all child entities in a hierarchy to which the deleted entity belongs; and

if an indication is received that the deletion of the entity was erroneous, replicating the updated entity in the first replica and the second replica.

20. A computer-readable medium in accordance with claim 19, wherein:

the update to the entity on the first replica comprises moving the entity from a first hierarchy to a second hierarchy in the first replica;

the deletion to the entity in the second replica comprises deletion the second hierarchy in the second replica;

replicating further comprises replicating the entity in the second hierarchy in the first replica and the second replica; and

deleting further comprises deleting the second hierarchy from the first replica and the second replica.