Systems and methods for the propagation of conflict resolution to enforce item convergence (i.e., data convergence)

• US 7,533,134 B2
• Filed: 09/01/2004
• Issued: 05/12/2009
• Est. Priority Date: 04/01/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev, Terry, Douglas B., Hudis, Irena, Jhaveri, Vivek Jawahir
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Yen; Syling
• Application Number:
  US10/932,474
• Publication Number:
  US 20050223117A1
• Time in Patent Office: 1,714 Days
• Field of Search: 707/10, 707202-204, 707/201, 707/8, 709/219, 709/236, 455/502, 455/462
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Various embodiments of the present invention are directed to systems and method for detecting conflicts and applying conflict resolutions during manual and automatic conflict resolution operations. Several embodiments are directed to preventing both: (a) non-convergence of conflict resolutions, where partners can end up in a divergent steady state (i.e. have different data in the absence of outstanding conflicts); and (b) a non-terminating ping-pong of conflict resolutions between partners (which can occur with certain inefficient solutions that continuously update metadata for each conflict resolution without end). Certain specific embodiments of the present invention are directed to a method for maintaining knowledge that guarantees convergence of data, even when different partners apply different conflict resolutions.

Claims

1. A computer-implemented method for synchronizing change unit data between a first computer system and a second computer system, said first computer system comprising a first replica of said change unit data and a first metadata corresponding to said first replica, said first metadata comprising a first change version, a first conflict resolution version, and a first awareness vector, and said second computer system comprising a second replica of said change unit data and a second metadata corresponding to said second replica, said second metadata comprising a second change version, a second conflict resolution version, and a second awareness vector, said method comprising the following steps:

sending the first awareness vector from the first computer system to the second computer system;

determining if the first awareness vector contains the second change version and the second conflict resolution version and, if so, sending the second replica of said change unit data from the second computer system to the first computer system;

sending the second metadata from the second computer system to the first computer system;

if the second replica of said change unit data was not sent from the second computer system to the first computer system, updating the first awareness vector and ending the method for synchronizing change unit data;

if the second replica of said change unit data was sent from the second computer system to the first computer system, determining whether the first awareness vector contains the second change version and the second conflict resolution version and, if so, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector contains the second change version but not the second conflict resolution version, then determining whether the second awareness vector contains at least one version reflected by the first change version and, if not, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector does not contain the second change version or if the second awareness vector contains at least one version reflected by the first change version, then determining whether the second awareness vector contains the first change version and, if so, then applying the second replica of the change unit data and updating the metadata if the first awareness vector does not contain at least one version reflected by the second change version or if the first awareness vector contains at least one version reflected by the second change version and the second awareness vector contains the first conflict resolution version;

if the second awareness vector does not contain the first change version but the first awareness vector contains the second change version or if the second awareness vector does not contain the first conflict resolution version, then deterministically selecting a change unit solution to ensure convergence of change unit data;

if the first awareness vector does not contain the second change version and the second awareness vector does not contain the first change version, then determining that a conflict has occurred and resolving the conflict; and

,

updating the first replica of said change unit data and the first metadata and, if a conflict has arisen, further updating the first conflict resolution version and the first awareness vector to reflect a conflict resolution and thereby preventing a divergent state from arising.

2. A computer-readable storage medium comprising computer-readable instructions when executed by a processor cause the processor to perform a method of synchronizing change unit data between a first computer system and a second computer system, said first computer system comprising a first replica of said change unit data and a first metadata corresponding to said first replica, said first metadata comprising a first change version, a first conflict resolution version, and a first awareness vector, and said second computer system comprising a second replica of said change unit data and a second metadata corresponding to said second replica, said second metadata comprising a second change version, a second conflict resolution version, and a second awareness vector, said computer-readable instructions comprising instructions for:

sending the first awareness vector from the first computer system to the second computer system;

determining if the first awareness vector contains the second change version and the second conflict resolution version and, if so, sending the second replica of said change unit data from the second computer system to the first computer system;

sending the second metadata from the second computer system to the first computer system;

if the second replica of said change unit data was not sent from the second computer system to the first computer system, updating the first awareness vector and ending the method for synchronizing change unit data;

if the second replica of said change unit data was sent from the second computer system to the first computer system, determining whether the first awareness vector contains the second change version and the second conflict resolution version and, if so, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector contains the second change version but not the second conflict resolution version, then determining whether the second awareness vector contains at least one version reflected by the first change version and, if not, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector does not contain the second change version or if the second awareness vector contains at least one version reflected by the first change version, then determining whether the second awareness vector contains the first change version and, if so, then applying the second replica of the change unit data and updating the metadata if the first awareness vector does not contain at least one version reflected by the second change version or if the first awareness vector contains at least one version reflected by the second change version and the second awareness vector contains the first conflict resolution version;

if the second awareness vector does not contain the first change version but the first awareness vector contains the second change version or if the second awareness vector does not contain the first conflict resolution version, then deterministically selecting a change unit solution to ensure convergence of change unit data;

if the first awareness vector does not contain the second change version and the second awareness vector does not contain the first change version, then determining that a conflict has occurred and resolving the conflict; and

updating the first replica of said change unit data and the first metadata and, if a conflict has arisen, further updating the first conflict resolution version and the first awareness vector to reflect a conflict resolution and thereby preventing a divergent state from arising.

3. A hardware control device for synchronizing change unit data between a first computer system and a second computer system, said first computer system comprising a first replica of said change unit data and a first metadata corresponding to said first replica, said first metadata comprising a first change version, a first conflict resolution version, and a first awareness vector, and said second computer system comprising a second replica of said change unit data and a second metadata corresponding to said second replica, said second metadata comprising a second change version, a second conflict resolution version, and a second awareness vector, said hardware control device comprising means for:

sending the first awareness vector from the first computer system to the second computer system;

determining if the first awareness vector contains the second change version and the second conflict resolution version and, if so, sending the second replica of said change unit data from the second computer system to the first computer system;

sending the second metadata from the second computer system to the first computer system;

if the second replica of said change unit data was not sent from the second computer system to the first computer system, updating the first awareness vector and ending the method for synchronizing change unit data;

if the second replica of said change unit data was sent from the second computer system to the first computer system, determining whether the first awareness vector contains the second change version and the second conflict resolution version and, if so, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector contains the second change version but not the second conflict resolution version, then determining whether the second awareness vector contains at least one version reflected by the first change version and, if not, updating the first awareness vector and ending the method for synchronizing change unit data;

if the first awareness vector does not contain the second change version or if the second awareness vector contains at least one version reflected by the first change version, then determining whether the second awareness vector contains the first change version and, if so, then applying the second replica of the change unit data and updating the metadata if the first awareness vector does not contain at least one version reflected by the second change version or if the first awareness vector contains at least one version reflected by the second change version and the second awareness vector contains the first conflict resolution version;

if the second awareness vector does not contain the first change version but the first awareness vector contains the second change version or if the second awareness vector does not contain the first conflict resolution version, then deterministically selecting a change unit solution to ensure convergence of change unit data;

if the first awareness vector does not contain the second change version and the second awareness vector does not contain the first change version, then determining that a conflict has occurred and resolving the conflict;

and

updating the first replica of said change unit data and the first metadata and, if a conflict has arisen, further updating the first conflict resolution version and the first awareness vector to reflect a conflict resolution and thereby preventing a divergent state from arising.