METHOD AND APPARATUS FOR DETERMINING COMPATIBLE VERSIONS OF DEPENDENT ENTITIES IN A COMPUTER SYSTEM

• US 20120272228A1
• Filed: 04/20/2011
• Published: 10/25/2012
• Est. Priority Date: 04/20/2011
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gullapalli, Ravi Kumar, Chacko Poriyath, Joby, MARNDI, Raj Narayan, Hassan, Sathyamurthy Dattahreya
• Granted Patent: US 8,997,084 B2
• Time in Patent Office: Days
• US Class Current: 717/170
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 9/44536 Selecting among different versions

Abstract

A computer executed method of determining compatible versions of dependent entities of a root entity having a specified version in a computer system. The method comprises building a directed graph containing dependent entities and dividing the directed graph into multiple levels. Compatible versions are determined for entities in upper levels of the directed graph before determining compatible versions for entities in lower levels of the directed graph.

Claims

1. A computer executed method of determining compatible versions of dependent entities of a root entity having a specified version in a computer system, the method comprising:

building a directed graph comprising the dependent entities;

dividing the directed graph into multiple levels;

dividing each level into one or more isolated subsets;

determining compatible versions for entities in upper levels of the directed graph before determining compatible versions for entities in lower levels of the directed graph.

2. The method of claim 1 wherein building the directed graph comprises:

representing the entities by nodes and dependency relationships between the entities by edges; and

putting a directed edge from a first node to a second node which is dependent on the first node and referring the first node as a parent node and the second node as a child node.

3. The method of claim 2 wherein the directed graph is divided into levels in such a way that no node of a given level is dependent on a node of a lower level.

4. The method of claim 3 wherein dividing the directed graph into multiple levels comprises:

putting a root node representing the root entity in the first level of the directed graph and all of said root node'"'"'s child nodes into a new level and then for each level of the directed graph;

a. including in the current level all nodes which are interdependent directly or indirectly with the nodes already included in the current level;

b. pushing into a next level of the directed graph all those nodes from the current level that are dependent on nodes which have not yet been assigned to a level; and

c. putting all the child nodes of parent nodes in the current level into the next level of the directed graph if said child nodes have not already assigned to a level; and

repeating a) to c) until all nodes have been assigned to a level of the directed graph.

5. The method of claim 1 wherein dividing each level into one or more isolated subsets comprises grouping together nodes which are in the same level and which share the same parent into the same isolated subset.

6. The method of claim 5 wherein dividing each level into one or more isolated subsets comprises forming groups of nodes of the same level which share the same parent and merging of two groups of the same level if there exists a common node between them or if a node from one of said two groups is dependent on a node of the other of said two groups.

7. The method of claim 1 wherein determining compatible versions comprises determining compatible versions of entities belonging to isolated subsets of the same level in sequence or in parallel.

8. The method of claim 1, wherein determining compatible versions of entities in an isolated subset comprises assigning versions to entities whose parents have already been assigned based on simple redundancy resolution.

9. The method of claim 1, wherein determining compatible versions of entities in an isolated subset further comprises performing triangular dependency resolution if two entities are mutually dependent and share a common parent whose version has already been assigned.

10. The method of claim 1, wherein determining compatible versions of entities in an isolated subset further comprises performing cyclic dependency resolution for entities belonging to a plurality of entities which are dependent on each other in a cycle.

11. The method of claim 8 wherein simple dependency resolution comprises considering the upper and lower limits of the compatibility ranges of a dependent entity with respect to each of its parent entities and assigning to said dependent entity the highest version of said lower limits which is below said upper limits of said compatibility ranges.

12. The method of claim 9 wherein a first entity is a common parent of second and third entities and said second and third entities are mutually dependent on each other;

and wherein triangular dependency resolution of the second and third entities comprises;

a. assigning to the second entity the lowest version which is compatible with the first entity;

b. assigning to the third entity a version which is compatible with the already assigned version of the first entity and the version assigned to the second entity in step a), if there exists overlap in the compatibility ranges of the first and second entities with respect to the third entity;

c. assigning entities in reverse of above mentioned order if there does not exist overlap in the compatibility ranges of the first and second entities with respect to the third entity; and

d. indicating a result of no compatibility if the compatibility ranges do not overlap even after reversing the order.

13. The method of claim 12 wherein in step b) the third entity is assigned the highest of the lower limits of the overlapping compatibility ranges of the first and second entities with respect to the third entity.

14. The method of claim 10, wherein cyclic dependency resolution comprises:

assigning a compatible version to any one entity in the cycle, all of whose parents except for a parent node that is part of the cycle, having already been assigned versions;

assigning a version to the next entity in the cycle based on the recently assigned version of the parent entity in the cycle and any other parent entities outside the cycle, if they exist;

continuing this process until an entity is not assigned or not reassigned a new version.

15. An apparatus comprising a processor, a memory in communication with the processor, and computer executable instructions stored in the memory and executable by the processor to:

build a directed graph containing dependent entities;

divide the directed graph into multiple levels and each level into one or more isolated subsets;

assign compatible versions for entities in upper levels of the directed graph before assigning compatible versions for entities in lower levels of the directed graph.

16. A method of upgrading a computer system comprising a root entity and a set of other entities that are dependent on the root entity, the method comprising:

specifying a change to the root entity or receiving information relating to a specified change for the root entity;

building a directed graph of the entities and splitting the directed graph into levels;

grouping entities within the same level of the graph into one or more isolated subsets, each isolated subset comprising entities which are directly dependent on a common parent entity;

and determining consequential changes to the entities in each isolated subset, consequential changes for the entities in isolated subsets in upper levels of the directed graph being determined before consequential changes for entities in isolated subsets in lower levels of the directed graph.

17. The method of claim 16 further comprising implementing the consequential changes or scheduling the consequential changes to be implemented in an upgrade.