1. A method for provisioning a new virtual machine instance, the method comprising: receiving, at a host machine, a first message from a remote processor, wherein the first message includes an inquiry into whether the host machine has an empty slot available to host the new virtual machine instance; sending, by the host machine, a first response message to the remote processor indicating an availability of at least one empty slot; receiving, by the host machine, a second message from the remote processor, wherein the second message includes an inquiry into a percentage of an image of the new virtual machine instance available in local storage on the host machine, wherein the image comprises a plurality of clusters; calculating, by the host machine, the percentage of the image of the new virtual machine instance available in a local storage of the host machine, wherein the calculating utilizes a consultation to a similarity matrix stored on the host machine and comprising: a plurality of rows, each of the plurality of rows corresponding to a given cluster of the plurality of clusters; a plurality of columns, each of the plurality of columns corresponding to a given image of the each image; and at each intersection of one of the plurality of rows and one of the plurality of columns, an indicator indicating whether the given cluster occurs in the given image; sending, by the host machine, a second response message to the remote processor, the second response message indicating the percentage of the image of the new virtual machine instance available in local storage on the respective host.