1. A method comprising: executing virtual machines that are each configured to communicate with each other over a virtual network and are configured to handle requests associated with at least a destination address on a public network; operating gateways, including a first gateway and a separate and distinct second gateway, that are each configured to provide connectivity between the virtual network and the public network, that each separately and independently implement a consistent mapping operation to perform load-balancing among the virtual machines, wherein at the first gateway a first mapping data structure includes entries reflecting mappings between source addresses and virtual machines, and wherein at the second gateway a distinct second mapping data structure includes entries reflecting mappings between source addresses and virtual machines; independently obtaining health information of the virtual machines, by each of the first gateway and the second gateway; independently determining, based on the health information of the virtual machines, a group of healthy virtual machines comprising two or more of the virtual machines, by each of the first gateway and the second gateway; receiving, at the first gateway, a first incoming packet that includes a source address and the destination address, wherein the first mapping data structure does not include, at a time of receiving the first incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines; selecting, at the first gateway, a handling virtual machine from among the group of healthy virtual machines that was independently determined by the first gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the first gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the first gateway; forwarding, by the first gateway, the first incoming packet to the handling virtual machine over the virtual network; creating, in the first mapping data structure at the first gateway, a first mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine; receiving at the second gateway, a second incoming packet that includes the same source address and the same destination address as the first incoming packet, wherein the second mapping data structure does not include, at a time of receiving the second incoming packet, any entry that reflects a mapping between the source address and any of the virtual machines, and the first mapping data structure does include the first mapping entry; selecting, solely by operation of the second gateway independent of the first gateway and of the first mapping data structure, the same handling virtual machine from among the group of healthy virtual machines that was independently determined by the second gateway, based on an output of the consistent mapping operation that is separately and independently implemented by the second gateway, wherein the output is obtained given the source address, the destination address, and the group of healthy virtual machines that was independently determined by the second gateway; forwarding, by the second gateway, the second incoming packet to the handling virtual machine over the virtual network; and creating, in the second mapping data structure at the second gateway, a second mapping entry reflecting a mapping between the source address and the handling virtual machine to forward one or more additional incoming packets, each including the source address and the destination address, to the handling virtual machine.