HyParView: a membership protocol for reliable gossip-based broadcast
📜 Abstract
Gossip, or epidemic, protocols have emerged as a powerful strategy to implement highly scalable and resilient reliable broadcast primitives. Due to scalability reasons, each participant in a gossip protocol maintains a partial view of the system. The reliability of the gossip protocol depends upon some critical properties of these views, such as degree distribution and clustering coefficient. Several algorithms have been proposed to maintain partial views for gossip protocols. In this paper, we show that under a high number of faults, these algorithms take a long time to restore the desirable view properties. To address this problem, we present HyParView, a new membership protocol to support gossip-based broadcast that ensures high levels of reliability even in the presence of high rates of node failure. The HyParView protocol is based on a novel approach that relies in the use of two distinct partial views, which are maintained with different goals by different strategies.
✨ Summary
Paper summary
HyParView introduces a hybrid membership protocol for gossip-based broadcast. Each node maintains two partial views: a small, symmetric active view used for message dissemination and a larger passive view containing backup peers. The active view is maintained reactively, using TCP connections both for reliable transport and for rapid failure detection. The passive view is maintained cyclically through shuffle operations and supplies replacement peers when active neighbors fail.
The design combines randomized overlay construction with deterministic flooding over the active-view graph. This allows the system to use a smaller fanout while retaining high delivery reliability, provided the active overlay remains connected. In the paper’s PeerSim simulations with 10,000 nodes, the evaluated configuration used an active view of 5 nodes, a passive view of 30 nodes, an active random-walk length of 6, and a passive random-walk length of 3. HyParView recovered its pre-failure reliability in one or two membership cycles for failure levels below 80%, and the experiments reported approximately 90% delivery to surviving nodes even when 95% of nodes failed. These results are simulation results under the paper’s stated model, not general guarantees.
Subsequent influence and use
The protocol has been adopted or reimplemented in later distributed-systems software. The Partisan BEAM distribution layer includes a modified HyParView-based peer-service manager for partially connected, high-churn clusters. (lasp-lang.readme.io) The Babel protocol-development framework used HyParView as the membership component in a peer-to-peer dissemination case study, where it was combined with a separate flooding protocol. (asc.di.fct.unl.pt) Public implementations also exist in Go, Rust, Kotlin, and Elixir, including HashiCorp’s HyParView repository and an implementation used in the iroh-gossip codebase. (github.com) These references provide concrete evidence of continued implementation and systems use; they do not by themselves establish a universal standardization or broad commercial deployment of the protocol.
The conference publication is indexed as DSN 2007, DOI 10.1109/DSN.2007.56, with pages 419–429. (dblp.org)