Balancing Gossip Exchanges in Networks with Firewalls.
J. Leitão, R. van Renesse and L. Rodrigues.
Selected sections of this report were published in the Proceedings of
the 9th International Workshop on Peer-to-Peer Systems (IPTPS
'10), San Jose, CA, USA, 27 April, 2010.
Gossip protocols are an important building block of many large-scale
systems. They have inherent load-balancing properties as long as nodes
are deployed over a network with a ``flat'' topology, that is, a
topology where any pair of nodes may engage in a gossip
exchange. Unfortunately, the Internet is not flat in the sense that
firewalls and NAT boxes block many peer-wise interactions. In
particular, nodes that are behind a firewall can initiate
communication with nodes on the public Internet, but not vice
versa. This may easily unbalance the number of gossip exchanges in
which nodes are involved. In particular, nodes in well connected
regions of the network tend to participate in many more interactions
than other nodes and may suffer from resource exhaustion.
In this paper we present and evaluate a new approach to balance gossip
exchanges in networks with firewalls. Our solution requires only local
information and has no coordination overhead, allowing nodes to
participate in a similar number of gossip exchanges independent of the
Also available extended report (pdf)