Epidemic Broadcast Trees

📜 Abstract

We present a reliable and efficient multicast protocol, called T-Rex, which can tolerate massive failures caused by process crashes or network partitions in large systems. Traditional reliable multicast protocols, which guarantee that all members of a group receive a message, have been designed assuming that failures are rare events. However, outages at server farms (e.g., having thousands of servers), load-conscious batch schedulers, fast client mobility in wireless or ad-hoc settings, mis-configured firewalls, unanticipated cascading failures, catastrophic regional failures, and hostile attacks, can lead to massive network failures and partitions where such protocols may be ineffective. We examine whether epidemic multicast protocols can offer an effective solution to this problem and find, rather surprisingly, that they may not scale to million-node systems due to redundant message duplication. Therefore, we propose Epidemic Broadcast Trees (EBT), a approach communicating by growing logical trees in an epidemic fashion, creating message redundancy without overloading systems. These trees are self-healing and adapt to topology changes effectively without compromising message delivery guarantees.