Reconstituting a machine image separates constituent parts of a machine image, and for each part, determines whether an exact version of the part is available on the target machine. If an exact version of the part is not available on the target machine, an inexact part is looked for on the target machine. Whether an inexact part is found may be determined based on attribute policy specification and similarity computation. For the inexact part found on the target machine, any dependencies may be identified and processed as a part to be reconstituted for the machine image. If no exact part and no inexact part are found on the target machine, the part is transferred from a source machine to the target machine. A machine image is created based on parts.