When a private node behind a Network Address Traversal aka NAT, requests the information from a public node it will specify a shuffle request. In response the public node will send a shuffled response. Both the private node and the public node will update their states. If another node on the internet tries to issue a shuffle request to the private node behind the NAT, it will not pass through the NAT. This is the expected behavior for the Epidemic algorithms when they leverage a NAT.

The solutions for communicating with the private nodes in this manner can be achieved in one of two ways. The first technique involves a relay where the communications are relayed to the private node using a public relay node. The second method involves a NAT hole-punching algorithm to establish a direct connection to the private node using a public rendezvous node. The choice between the two is determined by latency and load.  Relaying has lower latency message exchange. It enables lower gossip cycle periods. It is also necessary in dynamic networks. The other method decreases load on the public nodes but this is not always the case. The load does not decrease if the shuffle messages are small.

Gozar is NAT aware peer sampling algorithm. Each private nodes connects to one or more public nodes called partners that act as a relay or rendezvous server on behalf of the private node. A node’s descriptor consists of both its own address, it’s NAT type, and its partners’ addresses at the time of the descriptor creation. When a node wants to gossip with a private node, it uses the partner addresses in its descriptor to communicate with the private node.

Epidemic algorithms are important techniques to solve problems in a dynamic large scale systems. They are scalable, simple and robust to node failures, message loss and transient network disruptions. The applications are aggregation, membership management, and topology management.