Gossip versus Deterministic Flooding: Low Message Overhead and High Reliability for Broadcasting on Small Networks

Abstract

Rumor mongering (also known as gossip) is an epidemiological protocol that implements broadcasting with a reliability that can be very high. Rumor mongering is attractive because it is generic, scalable, adapts well to failures and recoveries, and has a reliability that gracefully degrades with the number of failures in a run. However, rumor mongering uses random selection for communications. We study the impact of using random selection in this paper. We present a protocol that superficially resembles rumor mongering but is deterministic. We show that this new protocol has most of the same attractions as rumor mongering. The one attraction that rumor mongering has---namely graceful degradation---comes at a high cost in terms of the number of messages sent. We compare the two approaches both at an abstract level and in terms of how they perform in an Ethernet and small wide area network of Ethernets.