Epidemic Broadcast Trees
📜 Abstract
There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability.
✨ Summary
The paper introduces Plumtree, a push-lazy-push broadcast protocol that combines the efficiency of tree-based multicast with the resilience of epidemic gossip. It operates over a random, partially connected overlay maintained by a peer-sampling service such as HyParView.
Each node divides its overlay neighbors into eager and lazy peers. Full message payloads are sent eagerly along selected links, whose evolution forms a spanning broadcast tree. Lazy peers receive compact IHAVE announcements rather than the payload. If a node does not receive the corresponding payload through its eager links before a timeout, it sends a GRAFT request to a lazy neighbor, retrieves the message, and promotes that link into the eager tree. Duplicate payloads cause PRUNE messages, removing redundant eager links. This mechanism allows the protocol to construct, repair, and gradually optimize the tree without requiring a separate multicast infrastructure.
The protocol is evaluated through PeerSim simulations involving 10,000 nodes and a HyParView overlay. In stable operation, Plumtree reduces relative payload redundancy to approximately zero after tree construction, compared with a redundancy value near three for the evaluated eager-gossip baseline. It retains high reliability under continual failures, although failures increase delivery-hop variability and temporarily introduce redundant traffic during healing. Under massive failures, reliability degrades sharply when the underlying overlay becomes disconnected—particularly above roughly 70% simultaneous node failure—but the protocols recover after the overlay is repaired. Sender-specific trees provide the best latency, while shared trees can suffer from sender-location bias; the proposed optimization reduces this bias at the cost of additional control traffic.
The paper’s main contribution is the demonstration that a low-cost, self-organizing tree can be embedded within a resilient gossip overlay, using non-tree links both as a recovery mechanism and as a source of tree-healing information. The design influenced subsequent dissemination systems. The libp2p Episub specification explicitly adopts Plumtree for multicast-tree construction, repair, and optimization, combining it with HyParView-style membership management. (github.com) Plumtree was also adopted in the Riak distributed datastore’s cluster-metadata subsystem; an account from NOVA reports reduced redundant messaging and approximately 66% faster dissemination after adoption. (fct.unl.pt) Later implementations, including iroh-gossip and other open-source libraries, continue to use the eager/lazy peer split, IHAVE announcements, grafting, and pruning principles described in the paper. (docs.rs)