Hierarchical Probabilistic Multicast

Patrick Eugster, Rachid GuerraouiInfoscience 2001

Abstract

In large-scale distributed systems, traditional reliable broadcast protocols often struggle to maintain performance as the number of participants grows. While probabilistic (gossip-based) algorithms offer superior scalability by trading off absolute reliability for high-probability delivery, they are typically designed for system-wide broadcasts. This paper presents hpmcast (Hierarchical Probabilistic Multicast), a novel algorithm designed to efficiently multicast events to specific subsets of a system. By leveraging a hierarchical membership structure, hpmcast optimizes for network locality and memory efficiency while maintaining the robust reliability characteristic of epidemic protocols.

Introduction

Disseminating information across massive networks involves a fundamental tension between reliability and scalability. Traditional deterministic protocols provide strong delivery guarantees but incur high overhead, often failing beyond a few hundred nodes. In contrast, gossip-based algorithms—inspired by the spread of epidemics—decentralize the retransmission effort, allowing systems to scale to thousands of nodes.

However, most existing gossip protocols focus on broadcasting to all participants. In content-based dissemination systems, users often require multicasting, where messages are only relevant to a specific subset. Applying standard gossip to multicasting usually results in two inefficient extremes: "Receiver Filtering" (wasting bandwidth on uninterested nodes) or "Sender Filtering" (requiring every node to maintain a massive, global view of all participants). This paper introduces hpmcast to bridge this gap.

The hpmcast Architecture

The Hierarchical Probabilistic Multicast (hpmcast) protocol addresses these inefficiencies by organizing participants into a tree-like hierarchy based on network proximity, such as IP addresses.

Hierarchical Membership and Delegates

Instead of a flat peer-to-peer network, hpmcast groups nodes into subsystems. Within each subsystem, a small number of nodes ($R$) are designated as delegates. These delegates represent their local group at higher levels of the hierarchy. This structure significantly reduces the memory footprint for individual nodes; rather than storing the addresses of every participant in a 10,000-node system, a node only needs to know its immediate peers and the delegates of its ancestral subsystems.

Dissemination Logic

Information flows through the hierarchy in a level-wise fashion:

  1. Top-Down Spread: A message originates or is injected at a high level and is gossiped among delegates.
  2. Feigned Multicast: To ensure the message reaches the intended subset, delegates act as "feigned" interested parties. Even if a delegate is not personally interested in the content, it facilitates the spread to its underlying subsystem if that subsystem contains interested members.
  3. Local Saturation: Once the message reaches the target subsystem, it is gossiped among the actual interested participants.

Overcoming the "Small Audience" Trap

A significant challenge in probabilistic multicasting is the "Small Audience" trap. Gossip protocols rely on the "law of large numbers" to ensure reliability. When the fraction of interested participants is very small, there are not enough "infected" nodes to sustain the epidemic, causing the message to die out prematurely.

To counter this, hpmcast employs an audience-boosting optimization. If the number of interested participants falls below a specific threshold ($D$), the protocol artificially includes a set of non-interested participants in the gossip pool. This "boosts" the message's reach until it achieves a stable spread, ensuring high reliability even for niche content.

Evaluation and Results

The authors evaluated hpmcast using stochastic analysis (Markov chains) and simulations of systems with approximately 10,000 participants.

  • Memory Scalability: The hierarchical approach reduces the required view size from $O(n)$ to $O(l \cdot R \cdot n^{1/l})$, where $l$ is the hierarchy depth. In practice, this allows nodes to manage massive networks with only a few dozen stored addresses.
  • Reliability: Simulations demonstrate that hpmcast maintains a reliability degree (the probability of reaching all interested participants) of over 0.999, provided the audience size is sufficient or the boosting optimization is active.
  • Fanout Impact: As with standard gossip, increasing the "fanout" ($F$)—the number of peers a node contacts per round—drastically improves reliability, though it follows a curve of diminishing returns.
  • Latency: Mathematical analysis proves that the hierarchical structure does not increase the number of rounds required to reach all participants compared to a flat broadcast, meaning structure is gained without a latency penalty.

Conclusion

hpmcast provides a scalable solution for the complex problem of multicasting in large, dynamic environments. By combining hierarchical membership with probabilistic dissemination, it achieves a balance between memory efficiency, network locality, and high reliability. While future work remains in automating parameter tuning and enhancing failure detection for high-churn environments, hpmcast represents a significant step forward for large-scale event-based systems.

Summary updated

Abstract

In our DACE project [6], diverging requirements expressed through QoS are mainly explored by a variety of different delivery semantics implemented through different dissemination algorithms ranging from "classic" Reliable Broadcast [18], to new and original algorithms, like the broadcast algorithm we introduce in [7], and which ensures reliable delivery of events despite network failures.While striving for strong scalability, we have invested considerable effort in exploring probabilistic (gossip-based) algorithms.These appear to be more adequate in the field of large scale event dissemination than traditional strongly reliable approaches like [18].Basically, probabilistic algorithms trade the strong reliability guarantees against very good scalability properties, yet still achieve a "pretty good degree of reliability" [12].Until now, most work on gossip-based algorithms considers broadcasting information to all participants in a system, paying little or no attention to individual and dynamic requirements, as typically encountered in contentbased dissemination.We present here Hierarchical Probabilistic Multicast (hpmcast [9]), a novel gossip-based algorithm which deals with the more complex case of multicasting an event to a subset of the system only.Requirements, such as limiting the consumption of local memory resources by view and message buffering, as well as exploiting locality (the proximity of participants) and redundancy (commonalities in interests of these participants), are all addressed.Though hpmcast has been motivated by our specific context of TPS, it is general enough to be applied to any context in which a strongly scalable primitive for event, message, or information dissemination is required.* This work is partially supported by Agilent Laboratories and Lombard Odier & Co.these acknowledgements converge. 1Moreover, such protocols hide any form of membership [2, 24], making them difficultly exploitable with more dynamic dissemination (filtering). Probabilistic AlgorithmsGossip, or rumor mongering algorithms [5], are a class of epidemiologic algorithms, which have been introduced as an alternative to such reliable network-level broadcast protocols.They have first been developed for replicated database consistency management, and have been mainly motivated by the desire of trading the strong reliability guarantees offered by costly deterministic algorithms against weaker reliability guarantees, but in return obtaining very good scalability properties.The analysis of such algorithms is usually based on stochastics similar to the theory of epidemics [3], where the execution is broken down into steps.Probabilities are associated to these steps, and such algorithms are therefore sometimes also referred to as probabilistic algorithms. Reliability DegreeThe "degree of reliability" is typically expressed by a probability; like the probability 1- of reaching all participants in the system for any given message, or by a probability 1- of reaching any given participant with any given message.Ideally, and are precisely quantifiable.A more precise measure, called -Reliability, based on the distribution of the probability of reaching a fraction of participants, is given in [12]. Basic ConceptsDecentralization is the key concept underlying the scalability properties of gossip-based broadcast algorithms, i.e., the overall load of (re)transmissions is reduced by decentralizing the effort.Participants are viewed as peers, symmetric in role, which are all equally eligible to forward information. 2This makes of gossip-based algorithms ideal candidates for systems with an underlying peer-to-peer model. ParametersMore precisely, retransmissions are initiated in most gossip-based algorithms by having every participant periodically, i.e., every P ms (step interval ), send information to a randomly chosen subset of participants inside the system (gossip subset ).The size F of the subset is usually fixed, and is commonly called fanout.Gossip algorithms differ in the number of times the same information is gossiped.Every participant might gossip the same information the same number of times, meaning that the number of repetitions is fixed.Alternatively, the same information might be forwarded only once by a same participant, and the longest causal chain of message forwards can be limited by fixing the number of hops H (or forwards).Also, the number of rounds T (step intervals) that a message remains in the system can be limited. ApproachesGossiping techniques have been proposed in a broad spectrum of contexts.Consequently, these algorithms vary a greate deal of further characteristics. Messages.Gossip-based algorithms differ in the kind of information that is shipped by gossiped messages (gossips).In early gossip algorithms, gossips reflect the sender's message buffer, including information about missing messages.Gossips have also been used to directly propagate the multicast payload (e.g., [10]), like events in the case of TPS.
BibTeX
@inproceedings{eugster2001hierarchical,
  author = {Patrick Eugster and Rachid Guerraoui},
  title = {{Hierarchical Probabilistic Multicast}},
  booktitle = {Infoscience},
  year = {2001},
}
Figure