Abstract
Gossip-based protocols provide a simple, scalable, and robust way to disseminate messages in large-scale systems. In such protocols, messages are spread in an epidemic manner. Gossiping may take place between nodes using push, pull, or a combination. Push-based systems achieve reasonable latency and high resilience to failures but may impose an unnecessarily large redundancy and overhead on the system. At the other extreme, pull-based protocols impose a lower overhead on the network at the price of increased latencies. A few hybrid approaches have been proposed—typically pushing control messages and pulling data—to avoid the redundancy of high-volume content and single-source streams. Yet, to the best of our knowledge, no other system intermingles push and pull in a multiple-senders scenario, in such a way that data messages of one help in carrying control messages of the other and in adaptively adjusting its rate of operation, further reducing overall cost and improving both on delays and robustness. In this paper, we propose an efficient generic push-pull dissemination protocol, Pulp, which combines the best of both worlds. Pulp exploits the efficiency of push approaches, while limiting redundant messages and therefore imposing a low overhead, as pull protocols do. Pulp leverages the dissemination of multiple messages from diverse sources: by exploiting the push phase of messages to transmit information about other disseminations, Pulp enables an efficient pulling of other messages, which themselves help in turn with the dissemination of pending messages. We deployed Pulp on a cluster and on PlanetLab. Our results demonstrate that Pulp achieves an appealing trade-off between coverage, message redundancy, and propagation delay.
Similar content being viewed by others
Notes
These probabilities are studied in the equivalent Coupons Collector problem, where a collector keeps selecting at random out of n different coupons with replacement, and the number of trials until all coupons have been selected at least once is measured.
In our experiments Cyclon converged in no more than 20 “cyclon rounds”, that is 100 s, and remained converged thereafter even at experiments involving churn.
In our experiments Cyclon traffic accounted for an average of 24 bytes/s per node, as explained in Section 4.1.
We chose this value of 4 to 5% as they allow for a low latency dissemination with only very few duplicates. Using larger values do not reduce the delays further but significantly increase duplicate counts. This choice is experimentally justified in Section 4.2.
Due to the high load on our cluster, periods are not exactly respected by the machine’s scheduler. This explains that the last message is sent at around 408 s and not 400 as expected.
References
Bhagwan R, Savage S, Voelker GM (2003) Understanding availability. In: Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS’03). Berkeley, CA, pp 256–267
Birman KP, Hayden M, Ozkasap O, Xiao Z, Budiu M, Minsky Y (1999) Bimodal multicast. ACM Trans Comput Syst 17(2):41–88
Bonald T, Massoulié L, Mathieu F, Perino D, Twigg A (2008) Epidemic live streaming: optimal performance trade-offs. In: SIGMETRICS. Annapolis, MA, pp 325–336
Champel M-L, Kermarrec A-M, Le Scouarnec N (2009) Fog: fighting the achilles’ heel of gossip protocols with fountain codes. In: SSS. Lyon, France, pp 180–194
Lo Cigno R, Russo A, Carra D (2008) On some fundamental properties of P2P push/pull protocols. In: Proceedings of the 2nd International Conference on Communications and Electronic (HUT-ICCE). HoiAn, Vietnam, pp 67–73
Cohen B (2003) Incentives build robustness in bittorrent. In: Proceedings of the 1st workshop on economics of Peer-to-Peer systems. Berkeley, CA
Demers A, Greene D, Hauser C, Irish W, Larson J, Shenker S, Sturgis H, Swinehart D, Terry D (1987) Epidemic algorithms for replicated database maintenance. In: Proceedings of the 6th annual ACM symposium on Principles of Distributed Computing (PODC’87). Vancouver, Canada, pp 1–12
Eugster P, Handurukande S, Guerraoui R, Kermarrec A-M, Kouznetsov P (2003) Lightweight probabilistic broadcast. ACM Trans Comput Syst 21(4):341–374
Frey D, Guerraoui R, Kermarrec A-M, Mogensen M, Monod M, Quéma V (2008) Gossiping capabilities. Technical Report LPD-REPORT-2008-010, EPFL
Ganesh AJ, Kermarrec A-M, Massoulié L (2003) Peer-to-Peer membership management for gossip-based protocols. IEEE Trans Comput 52(2):139–149
Jelasity M, Voulgaris S, Guerraoui R, Kermarrec A-M, van Steen M (2007) Gossip-based peer sampling. ACM Trans Comput Syst 25(3). http://dl.acm.org/citation.cfm?id=1275520
Karp R, Schindelhauer C, Shenker S, Vocking B (2000) Randomized rumour spreading. In: IEEE proc 41st ann symp Foundations of Computer Science (FOCS), p 565
Kashyap S, Deb S, Naidu, KVM, Rastogi R, Srinivasan A (2006) Efficient gossip-based aggregate computation. In: PODS ’06: proceedings of the 25th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems. ACM Press, New York, pp 308–317
Kermarrec A-M, Massoulié L, Ganesh AJ (2003) Probabilistic reliable dissemination in large-scale systems. IEEE Trans Parallel Distrib Syst 14(3):139–149
Kermarrec A-M, Pace A, Quema V, Schiavoni V (2009) Nat-resilient gossip peer sampling. In: ICDCS ’09: proceedings of the 2009 29th IEEE international conference on distributed computing systems. IEEE Computer Society, Washington, pp 360–367
Kermarrec A-M, van Steen M (2007) Gossiping in distributed systems. ACM Oper Syst Rev 41(5):2–7
Kostoulas D, Psaltoulis D, Gupta I, Birman KP, Demers AJ (2007) Active and passive techniques for group size estimation in large-scale and dynamic distributed systems. J Syst Softw 80(10):1639–1658
Li B, Qu Y, Keung GY, Xie S, Lin C, Liu J, Zhang X (2008) Inside the new coolstreaming: principles, measurements and performance implications. In: Proceedings of the 27th conference on computer communications (IEEE INFOCOM), pp 1031–1039
Li HC, Clement A, Marchetti M, Kapritsos M, Robison L, Alvisi L, Dahlin M (2008) Flightpath: obedience vs choice in cooperative services. In: Proceedings of the 8th USENIX symposium on Operating Systems Design and Implementation (OSDI ’08)
Li HC, Clement A, Wong EL, Napper J, Alvisi L, Dahlin M (2006) BAR gossip. In: Proc of 7th symposium on Operating System Design and Implementation (OSDI ’06), pp 191–2004
Leonini L, Rivière E, Felber P (2009) SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze). In: NSDI’09: proceedings of the 6th symposium on networked systems design and implementation. USENIX, pp 185–198
Lin M, Marzullo K (1999) Directional gossip: gossip in a wide area network. Technical Report CS1999-0622, University of California, San Diego
Lin M, Marzullo K, Masini S (2000) Gossip versus deterministic flooding: low-message overhead and high-reliability for broadcasting on small networks. In: Intl symposium on Distributed Computing (DISC 2000). Toledo, Spain, pp 85–89
Liu X, Lan J, Shenoy P, Ramaritham K (2006) Consistency maintenance in dynamic Peer-to-Peer overlay networks. Comput Networks 50(6):859–876
Locher T, Meier R, Schmid S, Wattenhofer R (2007) Push-to-pull Peer-to-Peer live streaming. In: Proceedings of DISC 2007: 21st international symposium on Distributed Computing. Lemosos, Cyprus
Pai V, Kumar K, Tamilmani K, Sambamurthy V, Mohr AE (2005) Chainsaw: eliminating trees from overlay multicast. In: IPTPS’05: the 4th international workshop on Peer-to-Peer systems, pp 127–140
Picconi F, Massoulié L (2008) Is there a future for mesh-based live video streaming? In: Proceedings of the 8th international conference on Peer-to-Peer computing (P2P’08). Aachen, Germany
Russo A, Lo Cigno R (2010) Delay-aware push/pull protocols for live video streaming in P2P systems. In: Proceedings of the IEEE International Conference on Communications (ICC)
Sanghavi S, Hajek B, Massoulié L (2007) Gossiping with multiple messages. In: Proceedings of the 29th conference on computer communications (IEEE INFOCOM), pp 2135–2143
Srinivasan R, Liang C, Ramamritham K (1998) Maintaining temporal coherency of virtual data warehouses. In: RTSS ’98: proceedings of the IEEE real-time systems symposium. IEEE Computer Society, Washington, DC, p 60
Urgaonkar B, Ninan AG, Raunak MS, Shenoy P, Ramamritham K (2001) Maintaining mutual consistency for cached web objects. In: ICDCS ’01: proceedings of the the 21st international conference on distributed computing systems. IEEE Computer Society, Washington, DC, pp 371–380
van Renesse R, Minsky Y, Hayden M (1998) A gossip-style failure detection service. In: IFIP (ed) Proc of Middleware, the IFIP international conference on distributed systems platforms and open distributed processing. The Lake District, UK, pp 55–70
Voulgaris S, Gavidia D, van Steen M (2005) CYCLON: inexpensive membership management for unstructured P2P overlays. J Netw Syst Manag 13(2):197–217
Zhang X, Liu J, Li B, Yum T-SP (2005) Coolstreaming/DONet: a data-driven overlay network for efficient live media streaming. In: Proceedings of the 24th conference on computer communications (IEEE INFOCOM), pp 2102–2111
Acknowledgements
This work was carried out during the tenure of Étienne Rivière’s ERCIM (European Research Consortium for Informatics and Mathematics) “Alain Bensoussan” fellowship. This work is supported in part by the Swiss National Foundation Grant 102819.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Felber, P., Kermarrec, AM., Leonini, L. et al. Pulp: An adaptive gossip-based dissemination protocol for multi-source message streams. Peer-to-Peer Netw. Appl. 5, 74–91 (2012). https://doi.org/10.1007/s12083-011-0110-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12083-011-0110-x