Lightweight probabilistic broadcast

By Patrick Th. Eugster, Rachid Guerraoui, S. Handurukande, Petr Kuznetsov, Anne-Marie Kermarrec. 2001 International Conference on Dependable Systems and Networks, 2001

651 citations recorded by the source corpus.

The growing interest in peer-to-peer applications has underlined the importance of scalability in modern distributed systems. Not surprisingly, much research effort has been invested in gossip-based broadcast protocols. These trade the traditional strong reliability guarantees against very good "scalability" properties. Scalability is in that context usually expressed in terms of throughput and delivery latency, but there is only little work on how to reduce the overhead of membership management on a large scale. The paper presents Lightweight Probabilistic Broadcast (lpbcast), a novel gossip-based broadcast algorithm which preserves the inherent throughput scalability of traditional gossip-based algorithms and adds a notion of membership management scalability: every process only knows a random subset of fixed size of the processes in the system. We formally analyze our broadcast algorithm in terms of scalability with respect to the size of individual views, and compare the analytical results both with simulations and concrete measurements.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/c2f502d9d51a0a37537ee188a9faf7b5219f9dec

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

A survey of attack and defense techniques for reputation systems (2009, background): “based dissemination techniques such as probabilistic broadcast [39], flooding [23], [31] and gossiping [8].”
SplitStream: high-bandwidth multicast in cooperative environments (2003, methodology): “SplitStream: High-Bandwidth Multicast in Cooperative Environments Miguel Castro1 Peter Druschel2 Anne-Marie Kermarrec1 Animesh Nandi2 Antony Rowstron1 Atul Singh2 1Microsoft Research, 7 J J Thomson Avenue, Cambridge, CB3 0FB, UK.”
Peer-to-Peer Membership Management for Gossip-Based Protocols (2003, methodology): “They have been used in various contexts such as publish-subscribe systems [12], distributed databases [10], distributed failure detection [26], distributed resource location [25], and virtual synchrony [15].”
Peer to Peer Multidimensional Overlays: Approximating Complex Structures (2007, background): “They have been successfully applied to a large number of settings from reliable broadcast [5] to overlay maintenance [8,12,23,25], and from aggregation [15] to system size estimation [22] and are now turned into a generic and sound substrate for building and maintaining large-scale overlay networks ”
Bullet: high bandwidth data dissemination using an overlay mesh (2003, methodology): “This technique does not use a tree for dissemination, and is similar to lpbcast [14] (recently improved to incorporate retrieval of data objects [13]).”
SCRIBE: The Design of a Large-Scale Event Notification Infrastructure (2001, background): “Appropriate algorithms and systems for scalable subscription management and scalable, reliable propagation of events are still an active research area [8–11].”
' s personal copy T-MAN : Gossip-based fast overlay topology construction q (2009, background): “For example, application-level multicast might need carefully controlled random networks or trees, depending on the multicast approach [1] [2].”
Wikipedia workload analysis for decentralized hosting (2009, methodology): “Updates are propagated throughout the system using a gossiping protocol [13], and merged using the Woot algorithm [25].”
CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays (2005, methodology): “This includes the work on lightweight probabilistic multicasting [4], as well as the Newscast system [7, 16].”
Source-location privacy in energy-constrained sensor network routing (2004, positive): “Probabilistic flooding [4, 7] was first proposed as an optimization of the baseline flooding technique to cut down energy consumption.”
Chainsaw: Eliminating Trees from Overlay Multicast (2005, background): “Lpbcast [8] extends pcast in that it requires nodes to have only partial membership information.”
Enhancing Source-Location Privacy in Sensor Network Routing (2005, positive): “Probabilistic flooding [16, 17] was first proposed as an optimization of the baseline flooding technique to cut down energy consumption.”
Survey of research towards robust peer-to-peer networks: Search methods (2006, neutral): “[125] P.”
Clique Gossiping (2017, background): “Gossip protocols provide a scalable and self-organized way of carrying out information dissemination over networks in the absence of centralized decision makers [1–6].”
Scribe: a large-scale and decentralized application-level multicast infrastructure (2002, background): “Algorithms and systems for scalable group management and scalable, reliable propagation of messages are still active research areas [6], [7], [8], [9], [10], [11].”
Gossip-based peer sampling (2007, methodology): “The framework is generic and can be used to instantiate known [Eugster et al. 2003; Jelasity et al. 2003; Voulgaris et al. 2005] and novel gossip-based membership implementations.”
A survey of autonomic communications (2006, background): “Modern distributed event-based approaches (such as Milan [G. Picco 2003; Eugster et al. 2003] or Siena [Carzaniga et al. 2001]) also support an eventbased style of programming by providing distributed event-dispatching services in the context of mobile ad hoc networks in which mobile nodes…”
The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations (2004, background): “A wide range of protocols fits into this framework and in particular the peer sampling components of the protocols Lpbcast [8] and Newscast [12] are specific instances of protocols within this framework.”
Wooki: A P2P Wiki-Based Collaborative Writing Tool (2007, positive): “Thus, we replace the standard probabilistic broadcast of [12] by the lightweight probabilistic broadcast (lpbcast) [13].”