Processes and systems are disclosed for leasing a producer virtual machine on behalf of a consumer virtual machine in an overlay network. The consumer host of the consumer virtual machine can communicate with a set of leasing agents to obtain the identity of a number of producer virtual machines capable of providing the consumer virtual machine with access to a service. When the consumer virtual machine attempts to communicate with a producer system, the consumer host can identify a producer host that hosts a target producer virtual machine and redirect a service request to the producer host.