research-article

MeanField analysis for the evaluation of gossip protocols

Authors:

Boudewijn R. HaverkortAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 36, Issue 3

Pages 31 - 39

https://doi.org/10.1145/1481506.1481513

Published: 30 November 2008 Publication History

Abstract

Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis of gossip protocols is mostly done using simulation, which tend to be expensive in computation time and memory consumption.

We introduce mean-field analysis as an analytical method to evaluate gossip protocols. Nodes in the network are represented by small identical stochastic models. Joining all nodes would result in an enormous stochastic process. If the number of nodes goes to infinity, however, mean-field analysis allows us to replace this intractably large stochastic process by a small deterministic process. This process approximates the behaviour of very large gossip networks, and can be evaluated using simple matrix-vector multiplications.

References

[1]

L. Afanassieva, S. Popov, and G. Fayolle. Models for transporation networks. J. of Math. Sciences, 84(3):1092--1103, 1997.

[2]

A. Allavena, A. Demers, and J. Hopcroft. Correctness of a gossip based membership protocol. In Proc. 24th Annual ACM Symp. on Principles of Distributed Computing (PODC'05), pages 292--301. ACM Press, 2005.

Digital Library

[3]

F. Baccelli, A. Chaintreau, D. De Vleeschauwer, and D. McDonald. A mean-field analysis of short lived interacting TCP flows. ACM SIGMETRICS Perform. Eval. Rev., 32(1):343--354, 2004.

Digital Library

[4]

F. Baccelli, A. Chaintreau, D. De Vleeschauwer, and D. McDonald. HTTP turbulence. AMS Networks and Heterogeneous Media, 1:1--40, 2006.

[5]

F. Baccelli, D. McDonald, and M. Lelarge. Metastable regimes for multiplexed TCP flows. In 42nd Allerton Conf. on Communication, Control, and Computing, 2004.

[6]

F. Baccelli, D. McDonald, and J. Reynier. A mean-field model for multiple TCP connections through a buffer implementing RED. Perform. Eval., 49(1-4):77--97, 2002.

Digital Library

[7]

R. Bakhshi, F. Bonnet, W. Fokkink, and B. Haverkort. Formal analysis techniques for gossiping protocols. ACM SIGOPS Oper. Syst. Rev., 41(5):28--36, 2007.

Digital Library

[8]

A. Bobbio, M. Gribaudo, and M. Telek. Analysis of large scale interacting systems by mean field method. In Proc. 5th Conf. on the Quantitative Evaluation of Systems (QEST'08), pages 215--224. IEEE Computer Society, 2008.

Digital Library

[9]

F. Bonnet. Performance analysis of Cyclon, an inexpensive membership management for unstructured P2P overlays. Master thesis, ENS Cachan Bretagne, University of Rennes, IRISA, 2006.

[10]

J.-Y. Le Boudec, D. McDonald, and J. Mundinger. A generic mean field convergence result for systems of interacting objects. In Proc. 4th Conf. on the Quantitative Evaluation of Systems (QEST'07), pages 3--18. IEEE Computer Society, 2007.

Digital Library

[11]

P. Costa, V. Gramoli, M. Jelasity, G. P. Jesi, E. Le Merrer, A. Montresor, and L. Querzoni. Exploring the interdisciplinary connections of gossip-based systems. ACM SIGOPS Oper. Syst. Rev., 41(5):51--60, 2007.

Digital Library

[12]

D. Dawson, J. Tang, and Y. Zhao. Balancing queues by mean field interaction. Queueing Syst. Theory & Appl., 49(3-4):335--361, 2005.

Digital Library

[13]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proc. 6th Annual ACM Symp. on Principles of Distributed Computing (PODC'87), pages 1--12. ACM Press, 1987.

Digital Library

[14]

D. Gavidia, S. Voulgaris, and M. van Steen. A Gossip-based Distributed News Service for Wireless Mesh Networks. In Proc. 3rd IEEE Conf. on Wireless On demand Network Syst. and Services (WONS'06), pages 59--67. IEEE Computer Society, 2006.

[15]

K. Iwanicki. Gossip-based dissemination of time. Master's thesis, Warsaw University and Vrije Universiteit Amsterdam, May 2005.

[16]

K. Iwanicki, M. van Steen, and S. Voulgaris. Gossip-based clock synchronization for large decentralized systems. In Proc. 2nd Workshop on Self-Managed Networks, Systems and Services (SelfMan 2006), volume 3996 of LNCS, pages 28--42. Springer, 2006.

Digital Library

[17]

M. Jelasity, R. Guerraoui, A.-M. Kermarrec, and M. van Steen. The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In Proc. 5th ACM/IFIP/USENIX Int. Middleware Conf. (Middleware'04), volume 3231 of LNCS, pages 79--98. Springer, 2004.

Digital Library

[18]

M. Jelasity, W. Kowalczyk, and M. van Steen. Newscast computing. Technical Report IR-CS-006, Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands., Novermber 2003.

[19]

M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219--252, 2005.

Digital Library

[20]

M. Jelasity, A. Montresor, G. P. Jesi, and S. Voulgaris. PeerSim: A peer-to-peer simulator. http://peersim.sourceforge.net/.

[21]

W. Kang, F. Kelly, N. Lee, and R. Williams. Fluid and Brownian approximations for an internet congestion control model. In Proc. 43rd IEEE Conf. on Decision and Control (CDC'04), volume 4, pages 3938--3943, 2004.

[22]

F. Karpelevich, E. Pechersky, and Y. Suhov. Dobrushin's approach to queueing network theory. J. of Applied Mathematics and Stochastic Analysis, 9(4):373--397, 1996.

[23]

A.-M. Kermarrec and M. van Steen. Gossiping in distributed systems. ACM SIGOPS Oper. Syst. Rev., 41(5):2--7, 2007.

Digital Library

[24]

S. Kumar and L. Massoulié. Integrating streaming and file-transfer internet traffic: fluid and diffusion approximations. Queueing Syst. Theory Appl., 55(4):195--205, 2007.

Digital Library

[25]

A. Martinoli, K. Easton, and W. Agassounon. Modeling Swarm Robotic Systems: A Case Study in Collaborative Distributed Manipulation. Int. Journal of Robotics Research, 23(4):415--436, 2004. Special Issue on Experimental Robotics, B. Siciliano, editor.

[26]

M. Puterman. Markov Decision Processes. Wiley, 1994.

[27]

I. Stojanovic, M. Sharif, and D. Starobinski. Data dissemination in wireless broadcast channels: Network coding r cooperation. In Proc. 41st Conf. on Information Sciences and Systems (CISS '07), pages 265--270. IEEE Press, 2007.

[28]

P. Tinnakornsrisuphap and A. Makowski. Limit behavior of ECN/RED gateways under a large number of TCP flows. In Proc. Conf. of the IEEE Computer and Communications Societies, volume 2, pages 873--883. IEEE Computer Society, 2003.

[29]

S. Voulgaris, D. Gavidia, and M. van Steen. Cyclon: Inexpensive membership management for unstructured P2P overlays. J. Network and Syst. Manage., 13(2):197--217, 2005.

[30]

N. Vvedenskaya and Y. Suhov. Dobrushin's mean-field approximation for a queue with dynamic routing. Markov Proc. Rel. Fields, 3(4):493--526, 1997.

[31]

Q. Zhang and D. Agrawal. Dynamic probabilistic broadcasting in MANETs. J. of Parallel and Distributed Computing, 65(2):220--233, 2005.

Digital Library

Cited By

Esterhuyse CMüller Tvan Binsbergen L(2024)JustAct: Actions Universally Justified by Partial Dynamic PoliciesFormal Techniques for Distributed Objects, Components, and Systems10.1007/978-3-031-62645-6_4(60-81)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62645-6_4
Bortolussi LHillston JLoreti M(2020)Fluid approximation of broadcasting systemsTheoretical Computer Science10.1016/j.tcs.2020.02.020Online publication date: Feb-2020
https://doi.org/10.1016/j.tcs.2020.02.020
Altman EAzad ABaşar TDe Pellegrini F(2013)Combined optimal control of activation and transmission in delay-tolerant networksIEEE/ACM Transactions on Networking10.1109/TNET.2012.220607921:2(482-494)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1109/TNET.2012.2206079
Show More Cited By

Index Terms

MeanField analysis for the evaluation of gossip protocols

Recommendations

Mean-field framework for performance evaluation of push-pull gossip protocols

Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis ...
Mean-Field Analysis for the Evaluation of Gossip Protocols
QEST '09: Proceedings of the 2009 Sixth International Conference on the Quantitative Evaluation of Systems

Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis ...
Heterogeneous gossip
Middleware '09: Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 36, Issue 3

December 2008

56 pages

ISSN:0163-5999

DOI:10.1145/1481506

Issue’s Table of Contents

Copyright © 2008 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 November 2008

Published in SIGMETRICS Volume 36, Issue 3

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Esterhuyse CMüller Tvan Binsbergen L(2024)JustAct: Actions Universally Justified by Partial Dynamic PoliciesFormal Techniques for Distributed Objects, Components, and Systems10.1007/978-3-031-62645-6_4(60-81)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62645-6_4
Bortolussi LHillston JLoreti M(2020)Fluid approximation of broadcasting systemsTheoretical Computer Science10.1016/j.tcs.2020.02.020Online publication date: Feb-2020
https://doi.org/10.1016/j.tcs.2020.02.020
Altman EAzad ABaşar TDe Pellegrini F(2013)Combined optimal control of activation and transmission in delay-tolerant networksIEEE/ACM Transactions on Networking10.1109/TNET.2012.220607921:2(482-494)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1109/TNET.2012.2206079
Yang Zhang Chong EHannig JEstep D(2013)Approximating Extremely Large Networks via Continuum LimitsIEEE Access10.1109/ACCESS.2013.22816681(577-595)Online publication date: 2013
https://doi.org/10.1109/ACCESS.2013.2281668
Bruneo DScarpa MBobbio ACerotti DGribaudo M(2012)Markovian agent modeling swarm intelligence algorithms in wireless sensor networksPerformance Evaluation10.1016/j.peva.2010.11.00769:3-4(135-149)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1016/j.peva.2010.11.007
Bakhshi RCloth LFokkink WHaverkort B(2011)Mean-field framework for performance evaluation of push-pull gossip protocolsPerformance Evaluation10.1016/j.peva.2010.08.02568:2(157-179)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1016/j.peva.2010.08.025
Zhengwei ZHuihui ZLin S(2010)Design of Multi-machine Communication System Based on TWIProceedings of the 2010 International Conference on Electrical and Control Engineering10.1109/iCECE.2010.876(3590-3593)Online publication date: 25-Jun-2010
https://dl.acm.org/doi/10.1109/iCECE.2010.876
Bakhshi REndrullis JEndrullis SFokkink WHaverkort B(2010)Automating the Mean-Field Method for Large Dynamic Gossip NetworksProceedings of the 2010 Seventh International Conference on the Quantitative Evaluation of Systems10.1109/QEST.2010.38(241-250)Online publication date: 15-Sep-2010
https://dl.acm.org/doi/10.1109/QEST.2010.38
Masci PChiaradonna SGiandomenico F(2010)Dependability Analysis of Diffusion Protocols in Wireless Networks with Heterogeneous Node CapabilitiesProceedings of the 2010 European Dependable Computing Conference10.1109/EDCC.2010.26(145-154)Online publication date: 28-Apr-2010
https://dl.acm.org/doi/10.1109/EDCC.2010.26
Altman EBaşar TDe Pellegrini F(2010)Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networksPerformance Evaluation10.1016/j.peva.2009.09.00167:4(299-317)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.peva.2009.09.001
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents