article

An adaptive peer-sampling protocol for building networks of browsers

Authors:

Brice Nédelec,

Achour MostéfaouiAuthors Info & Claims

World Wide Web, Volume 21, Issue 3

Pages 629 - 661

https://doi.org/10.1007/s11280-017-0478-5

Published: 01 May 2018 Publication History

Abstract

Peer-sampling protocols constitute a fundamental mechanism for a number of large-scale distributed applications. The recent introduction of WebRTC facilitated the deployment of decentralized applications over a network of browsers. However, deploying existing peer-sampling protocols on top of WebRTC raises issues about their lack of adaptiveness to sudden bursts of popularity over a network that does not manage addressing or routing. Spray is a novel random peer-sampling protocol that dynamically, quickly, and efficiently self-adapts to the network size. Our experiments show the flexibility of Spray and highlight its efficiency improvements at the cost of small overhead. We embedded Spray in a real-time decentralized editor running in browsers and ran experiments involving up to 600 communicating Web browsers. The results demonstrate that Spray significantly reduces the network traffic according to the number of participants and saves bandwidth.

References

[1]

Bailis, P., Ghodsi, A.: Eventual consistency today: Limitations, extensions, and beyond. Queue 11(3), 20:20---20:32 (2013)

Digital Library

[2]

Baquero, C., Almeida, P., Menezes, R., Jesus, P.: Extrema propagation: Fast distributed estimation of sums and network sizes. IEEE Trans. Parallel Distrib. Syst. 23(4), 668---675 (2012)

Digital Library

[3]

Bertier, M., Bonnet, F., Kermarrec, A.M., Leroy, V., Peri, S., Raynal, M.: D2ht: The best of both worlds, integrating rps and dht. In: Dependable Computing Conference (EDCC), 2010 European, pp. 135---144 (2010)

[4]

Birman, K.P., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., Minsky, Y.: Bimodal multicast. ACM Trans. Comput. Syst. 17(2), 41---88 (1999)

Digital Library

[5]

Bonnet, F., Tronel, F., Voulgaris, S.: Brief Announcement: Performance Analysis of Cyclon, an Inexpensive Membership Management for Unstructured P2P Overlays, pp. 560---562. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)

[6]

Camarillo, G., Maenpaa, J.: Self-tuning distributed hash table (dht) for resource location and discovery (reload) RFC 7363. Ericsson (2014)

[7]

Carvajal-Gómez, R., Frey, D., Simonin, M., Kermarrec, A.-M.: Web Information Systems Engineering --- WISE 2015: 16th International Conference, Miami, FL, USA, Proceedings, Part II, chapter WebGC Gossiping on Browsers Without a Server, pp. 332---336. Springer International Publishing, Cham (2015)

[8]

DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: Amazon's highly available key-value store. SIGOPS Oper. Syst. Rev. 41(6), 205---220 (2007)

Digital Library

[9]

Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pp. 1---12. ACM (1987)

Digital Library

[10]

Erdo's, P., Rényi, A.: On random graphs i. Publ. Math. Debrecen 6, 290---297 (1959)

[11]

Eugster, P.T., Guerraoui, R., Handurukande, S.B., Kouznetsov, P., Kermarrec, A.-M.: Lightweight probabilistic broadcast. ACM Trans. Comput. Syst. (TOCS) 21(4), 341---374 (2003)

Digital Library

[12]

Frey, D., Guerraoui, R., Kermarrec, A.-M., Monod, M., Quéma, V.: Stretching Gossip with Live Streaming. In: DSN (2009)

[13]

Frey, D., Guerraoui, R., Kermarrec, A.-M., Koldehofe, B., Mogensen, M., Monod, M., Quéma, V.: Heterogeneous Gossip. In: Middleware (2009)

[14]

Frey, D., Guerraoui, R., Kermarrec, A.-M., Monod, M.: Live Streaming with Gossip. Research report, Inria Rennes Bretagne Atlantique; RR-9039 (2017)

[15]

Ganesh, A., Kermarrec, A.-M., Massoulié, L.: Scamp: Peer-to-peer lightweight membership service for large-scale group communication. In: Crowcroft, J., Hofmann, M. (eds.) Networked Group Communication, volume 2233 of Lecture Notes in Computer Science, pp. 44---55. Springer Berlin Heidelberg (2001)

[16]

Ganesh, A., Kermarrec, A.-M., Massoulié, L.: Peer-to-peer membership management for gossip-based protocols. IEEE Trans. Comput. 52(2), 139---149 (2003)

Digital Library

[17]

Ganesh, A., Kermarrec, A.-M., Le Merrer, E., Massoulié, L.: Peer counting and sampling in overlay networks based on random walks. Distrib. Comput. 20(4), 267---278 (2007)

Digital Library

[18]

Jelasity, M., Guerraoui, R., Kermarrec, A.-M., Van Steen, M.: The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In: Jacobsen, H.-A. (ed.) Middleware 2004, volume 3231 of Lecture Notes in Computer Science, pp. 79---98. Springer-Verlag (2004)

Digital Library

[19]

Jelasity, M., Montresor, A.: Epidemic-style proactive aggregation in large overlay networks. In: Proceedings of the 24th International Conference on Distributed Computing Systems, pp. 102---109 (2004)

[20]

Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., Van Steen, M.: Gossip-based peer sampling. ACM Trans. Comput. Syst. (TOCS) 25(3), 8 (2007)

Digital Library

[21]

Jelasity, M., Montresor, A., Babaoglu, O.: T-man: Gossip-based fast overlay topology construction. Comput. Netw. 53(13), 2321---2339 (2009). Gossiping in Distributed Systems

Digital Library

[22]

Kermarrec, A.-M., Massoulié, L., Ganesh, A.: Probabilistic Reliable Dissemination in Large-Scale Systems. TPDS 14(3), 248---258 (2003)

[23]

Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pp. 163---170. ACM, NY, USA (2000)

Digital Library

[24]

Leitão, J., Pereira, J., Rodrigues, L.: Hyparview: A membership protocol for reliable gossip-based broadcast. In: 37th Annual IEEE/IFIP Intern ational Conference on Dependable Systems and Networks, 2007. DSN '07, pp. 419---429 (2007)

[25]

Li, H., Clement, A., Marchetti, M., Kapritsos, M., Robinson, L., Alvisi, L., Dahlin, M.: FlightPath: Obedience vs. Choice in Cooperative Services. In: OSDI (2008)

[26]

Monod, M.: Live streaming with gossip. PhD thesis, IC, Lausanne (2010)

[27]

Montresor, A., Jelasity, M., Babaoglu, O.: Robust aggregation protocols for large-scale overlay networks. In: International Conference on Dependable Systems and Networks, pp. 19---28 (2004)

[28]

Montresor, A., Jelasity, M.: Peersim: A scalable P2P simulator. In: Proceedings of the 9th International Conference on Peer-to-Peer (P2P'09), pp. 99---100, Seattle, WA (2009)

[29]

Nédelec, B., Molli, P., Mostéfaoui, A., Desmontils, E.: LSEQ: An adaptive structure for sequences in distributed collaborative editing. In: ACM, editor, 13th ACM Symposium on Document Engineering (2013)

[30]

Nédelec, B., Molli, P., Mostefaoui, A.: Crate: Writing stories together with our browsers. In: Proceedings of the 25th International Conference Companion on World Wide Web, WWW'16 Companion, pp. 231---234. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland (2016)

[31]

P. http://ozan.io/p/

[32]

Peerjs. http://peerjs.com

[33]

Roverso, R., Reale, R., El-Ansary, S., Haridi, S.: Smoothcache 2.0: Cdn-quality adaptive http live streaming on peer-to-peer overlays. In: Proceedings of the 6th ACM Multimedia Systems Conference, MMSys '15, pp. 61---72. ACM, NY, USA (2015)

[34]

Roverso, R., Högqvist, M.: Hive.js Browser-based distributed caching for adaptive video streaming. In: 2014 IEEE International Symposium on Multimedia (ISM), pp. 143---146 (2014)

[35]

Saito, Y., Shapiro, M.: Optimistic replication. ACM Comput. Surv. 37(1), 42---81 (2005)

Digital Library

[36]

Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types. Stabilization, Safety, and Security of Distributed Systems, pp. 386---400 (2011)

[37]

Tölgyesi, N., Jelasity, M.: Adaptive peer sampling with newscast. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009 Parallel Processing, volume 5704 of Lecture Notes in Computer Science, pp. 523---534. Springer Berlin Heidelberg (2009)

[38]

Voulgaris, S., Gavidia, D., Van Steen, M.: Cyclon: Inexpensive membership management for unstructured p2p overlays. J. Netw. Syst. Manag. 13(2), 197---217 (2005)

[39]

Voulgaris, S., Rivière, E., Kermarrec, A.-M., Van Steen, M.: Sub-2-Sub: Self-Organizing Content-Based Publish and Subscribe for Dynamic and Large Scale Collaborative Networks. Research Report RR-5772 INRIA (2005)

[40]

Voulgaris, S., Van Steen, M.: Epidemic-style management of semantic overlays for content-based searching. In: Cunha, J., Medeiros, P. (eds.) Euro-Par Parallel Processing, volume 3648 of Lecture Notes in Computer Science, p 2005. Springer Berlin Heidelberg (2005)

[41]

Watts, D.J., Strogatz, S.H.: Collective dynamics of `small-world' networks. Nature 393(6684), 440---442, 06 (1998)

[42]

Webrtc. http://www.Webrtc.org

[43]

Wuhib, F., Dam, M., Stadler, R., Clem, A.: Robust monitoring of network-wide aggregates through gossiping. IEEE Trans. Netw. Serv. Manag. 6(2), 95---109 (2009)

Digital Library

[44]

Zhang, L., Zhou, F., Mislove, A., Sundaram, R.: Maygh: Building a cdn from client Web browsers. In: Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys '13, pp. 281---294. ACM, NY, USA (2013)

[45]

Zhang, M., Zhang, Q., Sun, L., Yang, S.: Understanding the power of pull-based streaming protocol can we do better?. JSAC 25(9), 1678---1694 (2007)

Digital Library

Cited By

de Vos MFarhadkhani SGuerraoui RKermarrec APires RSharma ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Epidemic learningProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667689(36132-36164)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667689
Auvolat ABromberg YFrey DMvondo DTaïani F(2023)BasaltProceedings of the 24th International Middleware Conference10.1145/3590140.3629109(111-123)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629109
Antaris SRafailidis DAlhajj R(2020)VStreamDRLSProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381430(486-493)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381430
Show More Cited By

Recommendations

A connection management protocol for promoting cooperation in Peer-to-Peer networks

The existence of a high degree of free riding in Peer-to-Peer (P2P) networks is an important threat that should be addressed while designing P2P protocols. In this paper we propose a connection-based solution that will help to reduce the free riding ...
Ranking factors in peer-to-peer overlay networks

A large number of peer processes are distributed in a peer-to-peer (P2P) overlay network. It is difficult, maybe impossible for a peer to perceive the membership and location of every resource object due to the scalability and openness of a P2P network. ...
Building low-diameter peer-to-peer networks

Peer-to-peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. Current P2P networks (e.g., Gnutella) are constructed by participants following their own uncoordinated (and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image World Wide Web

World Wide Web Volume 21, Issue 3

May 2018

270 pages

ISSN:1386-145X

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 May 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Vos MFarhadkhani SGuerraoui RKermarrec APires RSharma ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Epidemic learningProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667689(36132-36164)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667689
Auvolat ABromberg YFrey DMvondo DTaïani F(2023)BasaltProceedings of the 24th International Middleware Conference10.1145/3590140.3629109(111-123)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629109
Antaris SRafailidis DAlhajj R(2020)VStreamDRLSProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381430(486-493)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381430
Grall ASkaf-Molli HMolli PPerrin M(2020)Collaborative SPARQL Query Processing for Decentralized Semantic DataDatabase and Expert Systems Applications10.1007/978-3-030-59003-1_21(320-335)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-59003-1_21

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents