Conflict resolution in a peer to peer network

• US 7,565,419 B1
• Filed: 11/22/2002
• Issued: 07/21/2009
• Est. Priority Date: 11/22/2002
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Joshi, Mahesh, van Rietschote, Hans F., Kwiatkowski, Marc P.
• Primary Examiner(s): Jacobs; Lashonda T
• Application Number:
  US10/302,291
• Time in Patent Office: 2,433 Days
• Field of Search: 709/203, 709/217, 709/219, 709223-224
• US Class Current: 709/223
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

An apparatus comprises a plurality of nodes interconnected as peers in a peer-to-peer network. At least some nodes are configured to update an object, thereby generating a plurality of versions of the object. Any of the plurality of nodes is configured to detect a conflict between a first version and a second version of the plurality of versions, and any of the plurality of nodes is configured to provide an indication of a resolution of the conflict to other ones of the plurality of nodes. Each version may be identified by a version descriptor that includes a version identifier (ID) and a parent version ID. If the version is the result of a conflict resolution, the version descriptor may also include a resolved version ID identifying the losing version. The resolved version ID may be used to prevent the raising of the same conflict after it has been resolved.

Claims

1. An apparatus comprising:

a plurality of nodes interconnected as peers in a peer-to-peer network, wherein each peer has equivalent capabilities and responsibilities, and wherein at least some of the plurality of nodes are configured to update an object, thereby generating a plurality of versions of the object;

wherein any of the plurality of nodes is configured to detect a conflict between content of a first version of the plurality of versions and content of a second version of the plurality of versions;

wherein any of the plurality of nodes is configured to provide an indication of a resolution of the conflict to other ones of the plurality of nodes; and

wherein the other ones of the plurality of nodes are configured not to raise the conflict again responsive to the indication of the resolution;

wherein each of the plurality of nodes that generates one of the plurality of versions is configured to locally generate a version identifier corresponding to that one of the plurality of versions, wherein the plurality of nodes is configured to detect the conflict using the version identifiers;

wherein each version of the plurality of versions is specified via a version descriptor comprising the version identifier generated for that version and a parent-version identifier identifying a parent version of the object from which that version is derived; and

wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein a first node of the plurality of nodes has the first version as a current version indicated by a first version identifier in the first node, and wherein the first node is configured to detect the conflict by tracing the version tree of the second version responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

2. The apparatus as recited in claim 1 wherein the first node detects the conflict if the first version identifier is not in the version tree of the second version.

3. The apparatus as recited in claim 1 wherein the indication of the resolution of the conflict comprises a third version descriptor transmitted by the first node, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the first version identifier as the parent version identifier.

4. The apparatus as recited in claim 3, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the second version identifier as the resolved version identifier.

5. The apparatus as recited in claim 1 wherein the version identifier comprises a logical timestamp.

6. The apparatus as recited in claim 5 wherein the version identifier further includes a universally unique identifier (uuid) of the object.

7. The apparatus as recited in claim 6 wherein the version identifier further includes a hash digest indicative of a content of the object.

8. The apparatus as recited in claim 1 wherein the object comprises a storage object.

9. The apparatus as recited in claim 1 wherein the object comprises an event in a reliable messaging system, and wherein updates to the object comprise messages.

10. The apparatus as recited in claim 1 wherein the object comprises a workflow object.

11. An apparatus comprising:

a plurality of nodes interconnected as peers in a peer-to-peer network, wherein at least some of the plurality of nodes are configured to update an object, thereby generating a plurality of versions of the object;

wherein each of the plurality of nodes that generates a respective one of the plurality of versions is configured to locally generate a version identifier corresponding to the respective one of the plurality of versions;

wherein the plurality of nodes are configured to detect conflicting updates in the plurality of versions responsive to the version identifiers corresponding to the conflicting updates;

wherein each version of the plurality of versions is specified via a version descriptor comprising the version identifier generated for that version and a parent version identifier identifying a parent version of the object from which that version is derived; and

wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein a first node of the plurality of nodes has a first version as a current version indicated by a first version identifier in the first node, and wherein the first node is configured to detect the conflict by tracing the version tree of a second version responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

12. The apparatus as recited in claim 11 wherein the first node detects the conflict if the first version identifier is not in the version tree of the second version.

13. The apparatus as recited in claim 11 wherein, in response to a resolution of a conflict, the first node is configured to transmit a third version descriptor, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the first version identifier as the parent version identifier.

14. The apparatus as recited in claim 13, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the second version identifier as the resolved version identifier.

15. In a plurality of nodes interconnected as peers in a peer-to-peer network, wherein each peer has equivalent capabilities and responsibilities, and wherein at least some of the plurality of nodes are configured to update an object, thereby generating a plurality of versions of the object, a method comprising:

detecting a conflict between content of a first version of the plurality of versions and content of a second version of the plurality of versions in any of the plurality of nodes;

providing an indication of a resolution of the conflict to other ones of the plurality of nodes from any of the plurality of nodes; and

not raising the conflict again in the other ones of the plurality of nodes responsive to the indication of the resolution;

each of the plurality of nodes that generates one of the plurality of versions locally generating a version identifier corresponding to that one of the plurality of versions, and wherein the detecting is performed using the version identifiers; and

wherein each version of the plurality of versions is specified via a version descriptor comprising the version identifier generated for that version and a parent version identifier identifying a parent version of the object from which that version is derived, and wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein a first node of the plurality of nodes has the first version as a current version indicated by a first version identifier in the first node, and wherein the detecting the conflict comprises tracing the version tree of the second version by the first node responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

16. The method as recited in claim 15 wherein the first node detects the conflict if the first version identifier is not in the version tree of the second version.

17. The method as recited in claim 15 wherein the indication of the resolution of the conflict comprises a third version descriptor transmitted by the first node, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the first version identifier as the parent version identifier.

18. The method as recited in claim 17, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the second version identifier as the resolved version identifier.

19. A computer readable medium comprising one or more instructions which, when executed in a first node of a plurality of nodes coupled as peers in a peer-to-peer network, wherein each peer has equivalent capabilities and responsibilities, a method comprising:

detect a conflict between content of a first version of a plurality of versions of an object and content of a second version of the plurality of versions;

provides an indication of a resolution of the conflict to other ones of the plurality of nodes; and

in response to receiving an indication of the resolution, do not raise the conflict again even if the conflict is detected again;

wherein the one or more instructions, when executed, locally generate a version identifier corresponding to one of the plurality of versions that is generated in the first node, wherein detecting a conflict is performed using version identifiers; and

wherein each version of the plurality of versions is specified via a version descriptor comprising the version identifier generated for that version and a parent version identifier identifying a parent version of the object from which that version is derived, and wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein the first node has the first version as a current version indicated by a first version identifier in the first node, and wherein the one or more instructions, when executed, detect the conflict by tracing the version tree of the second version responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

20. The computer readable medium as recited in claim 19 wherein the one or more instructions, when executed, detect the conflict if the first version identifier is not in the version tree of the second version.

21. The computer readable medium as recited in claim 19 wherein the indication of the resolution of the conflict comprises a third version descriptor transmitted by the first node, and wherein, responsive to resolving the first version as the winning version, the one or more instructions, when executed, include the first version identifier as the parent version identifier in the third version descriptor.

22. The computer readable medium as recited in claim 21, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the first version as the winning version, the one or more instructions, when executed, include the second version identifier as the resolved version identifier in the third version descriptor.

23. An apparatus comprising:

a plurality of nodes interconnected as peers in a peer-to-peer network, wherein at least some of the plurality of nodes are configured to update an object, thereby generating a plurality of versions of the object;

wherein each of the plurality of nodes that generates a respective one of the plurality of versions is configured to locally generate a version identifier corresponding to the respective one of the plurality of versions;

wherein each version of the plurality of versions is specified via a version descriptor comprising the version identifier generated for that version and a parent version identifier identifying a parent version of the object from which that version is derived; and

wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein a first node of the plurality of nodes that has a first version as a current version indicated by a first version identifier in the first node is configured to detect a conflict by tracing the version tree of a second version responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

24. The apparatus as recited in claim 23 wherein the first node detects the conflict if the first version identifier is not in the version tree of the second version.

25. The apparatus as recited in claim 23 wherein, in response to a resolution of a conflict, the first node is configured to transmit a third version descriptor, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the first version identifier as the parent version identifier.

26. The apparatus as recited in claim 25, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the first version as the winning version, the third version descriptor includes the second version identifier as the resolved version identifier.

27. The apparatus as recited in claim 23 wherein the other ones of the plurality of nodes are configured not to raise the conflict again responsive to the indication of the resolution.

28. The apparatus as recited in claim 23 wherein the version identifier comprises a logical timestamp.

29. The apparatus as recited in claim 28 wherein the version identifier further includes a universally unique identifier (uuid) of the object.

30. The apparatus as recited in claim 29 wherein the version identifier further includes a hash digest indicative of a content of the object.

31. The apparatus as recited in claim 23 wherein the object comprises a storage object.

32. The apparatus as recited in claim 23 wherein the object comprises an event in a reliable messaging system, and wherein updates to the object comprise messages.

33. The apparatus as recited in claim 23 wherein the object comprises a workflow object.

34. A computer accessible medium storing a plurality of instructions which, when executed on a node that is one of a plurality of nodes interconnected as peers in a peer-to-peer network:

locally generates a version identifier corresponding to a locally modified version of the object responsive to a modification of the object;

forms a version descriptor comprising the version identifier generated for the locally modified version and a parent version identifier identifying a parent version of the object from which that version is derived; and

wherein a version tree of the object is traceable via the parent version identifiers in the version descriptors for each version of the object, and wherein the plurality of instructions, when executed, detect a conflict by tracing the version tree of a second version responsive to receiving a second version identifier corresponding to the second version in a second version descriptor identifying the second version.

35. The computer accessible medium as recited in claim 34 wherein the conflict is detected if the version identifier is not in the version tree of the second version.

36. The computer accessible medium as recited in claim 34 wherein the plurality of instructions, when executed and in response to a resolution of a conflict, transmit a third version descriptor, and wherein, responsive to resolving the version as the winning version, the third version descriptor includes the version identifier as the parent version identifier.

37. The computer accessible medium as recited in claim 36, wherein the third version descriptor further includes a resolved version identifier indicative of the version for which the conflict has been resolved, and wherein, responsive to resolving the version as the winning version, the third version descriptor includes the second version identifier as the resolved version identifier.

38. The computer accessible medium as recited in claim 34 wherein the version identifier comprises a logical timestamp.

39. The computer accessible medium as recited in claim 38 wherein the version identifier further includes a universally unique identifier (uuid) of the object.

40. The computer accessible medium as recited in claim 39, wherein the version identifier further includes a hash digest indicative of a content of the object.

41. The computer accessible medium as recited in claim 34 wherein the object comprises a storage object.

42. The computer accessible medium as recited in claim 34 wherein the object comprises an event in a reliable messaging system, and wherein updates to the object comprise messages.

43. The computer accessible medium as recited in claim 34 wherein the object comprises a workflow object.