Fluid approximation of broadcasting systems.

*(English)*Zbl 1432.68020Summary: Nature-inspired paradigms have been proposed to design and forecast behaviour of open distributed systems, such as sensor networks and the internet of things. In these paradigms system behaviour emerges from (complex) interactions among a large number of agents. Modelling these interactions in terms of classical point-to-point communication is often not practical. This is due to the large scale and the open nature of the systems, which means that partners for point-to-point communication may not be available at any given time. Nevertheless the need for efficient formal verification of qualitative and quantitative properties of these systems is of utmost importance, especially given their proposed pervasive and transparent nature.

Carma is a recently proposed formal modelling language for open distributed systems, which is equipped with a broadcast communication in order to meet the communication challenges of such systems. The inclusion of quantitative information about the timing and probability of actions gives rise to models suitable for analysing questions such as the probability that information will achieve total coverage within a system, or the expected market share that might be gained by competing service providers relying on viral advertising. The ability to express models is not the only challenge, because the scale of the systems we are interested in often defies discrete state-based analysis techniques such as stochastic simulation. This is the problem that we address in this paper as we consider how to provide an efficient fluid approximation, supporting efficient and accurate quantitative analysis of large scale systems, for a language that incorporates broadcast communication.

Carma is a recently proposed formal modelling language for open distributed systems, which is equipped with a broadcast communication in order to meet the communication challenges of such systems. The inclusion of quantitative information about the timing and probability of actions gives rise to models suitable for analysing questions such as the probability that information will achieve total coverage within a system, or the expected market share that might be gained by competing service providers relying on viral advertising. The ability to express models is not the only challenge, because the scale of the systems we are interested in often defies discrete state-based analysis techniques such as stochastic simulation. This is the problem that we address in this paper as we consider how to provide an efficient fluid approximation, supporting efficient and accurate quantitative analysis of large scale systems, for a language that incorporates broadcast communication.

##### MSC:

68M14 | Distributed systems |

##### Keywords:

natural inspired paradigms; broadcast communication; stochastic process algebra; fluid approximation; population models; open distributed systems
PDF
BibTeX
XML
Cite

\textit{L. Bortolussi} et al., Theor. Comput. Sci. 816, 221--248 (2020; Zbl 1432.68020)

Full Text:
DOI

##### References:

[1] | Alrahman, Yehia Abd; De Nicola, Rocco; Loreti, Michele; Tiezzi, Francesco; Vigo, Roberto, A calculus for attribute-based communication, (Proceedings of the 30th Annual ACM Symposium on Applied Computing. Proceedings of the 30th Annual ACM Symposium on Applied Computing, Salamanca, Spain, April 13-17, 2015 (2015)), 1840-1845 |

[2] | Bakhshi, Rena, Gossiping Models - Formal Analysis of Epidemic Protocols (January 2011), Vrije Universiteit Amsterdam, PhD thesis |

[3] | Bakhshi, Rena; Cloth, Lucia; Fokkink, Wan; Haverkort, Boudewijn R., Meanfield analysis for the evaluation of gossip protocols, ACM SIGMETRICS Perform. Eval. Rev., 36, 3, 31-39 (2008) |

[4] | Ball, Karen; Kurtz, Thomas G.; Popovic, Lea; Rempala, Greg, Asymptotic analysis of multiscale approximations to reaction networks, Ann. Appl. Probab., 16, 4, 1925-1961 (2006) · Zbl 1118.92031 |

[5] | Bernardo, Marco; Gorrieri, Roberto, A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time, Theor. Comput. Sci., 202, 1-2, 1-54 (1998) · Zbl 0902.68075 |

[6] | Bortolussi, Luca, Hybrid behaviour of Markov population models, Inf. Comput., 247, 37-86 (April 2016) |

[7] | Bortolussi, Luca; Gast, Nicolas, Mean field approximation of uncertain stochastic models, (Dependable Systems and Networks, DSN 2016 (2016)), 287-298 · Zbl 1346.68217 |

[8] | Bortolussi, Luca; Hillston, Jane, Efficient checking of individual rewards properties in markov population models, (Quantitative Aspects of Programming Languages and Systems, QAPL 2015 (2015)), 32-47 · Zbl 1317.68108 |

[9] | Bortolussi, Luca; Hillston, Jane, Model checking single agent behaviours by fluid approximation, Inf. Comput., 242, 183-226 (2015) · Zbl 1317.68108 |

[10] | Bortolussi, Luca; Hillston, Jane; Latella, Diego; Massink, Mieke, Continuous approximation of collective system behaviour: a tutorial, Perform. Eval., 70, 5, 317-349 (2013) |

[11] | Bortolussi, Luca; Lanciani, Roberta, Model checking markov population models by central limit approximation, (Quantitative Evaluation of Systems (2013), Springer), 123-138 |

[12] | Bortolussi, Luca; De Nicola, Rocco; Galpin, Vasti; Gilmore, Stephen; Hillston, Jane; Latella, Diego; Loreti, Michele; Massink, Mieke, Carma: collective adaptive resource-sharing markovian agents, (Proc. of the Workshop on Quantitative Analysis of Programming Languages 2015. Proc. of the Workshop on Quantitative Analysis of Programming Languages 2015, EPTCS, vol. 194 (2015)), 16-31 |

[13] | Bortolussi, Luca; Policriti, Alberto, Stochastic concurrent constraint programming and differential equations, Electron. Notes Theor. Comput. Sci., 190, 3, 27-42 (2007) · Zbl 1279.92031 |

[14] | Bruneo, Dario; Scarpa, Marco; Bobbio, Andrea; Cerotti, Davide; Gribaudo, Marco, Markovian agent modeling swarm intelligence algorithms in wireless sensor networks, Perform. Eval., 69, 3-4, 135-149 (2012) |

[15] | Cianci, Christopher M.; Raemy, Xavier; Pugh, Jim; Martinoli, Alcherio, Communication in a swarm of miniature robots: the e-puck as an educational tool for swarm robotics, (Swarm Robotics, Second International Workshop, SAB 2006, Rome, Italy, September 30-October 1, 2006, Revised Selected Papers. Swarm Robotics, Second International Workshop, SAB 2006, Rome, Italy, September 30-October 1, 2006, Revised Selected Papers, Lecture Notes in Computer Science, vol. 4433 (2007), Springer), 103-115 |

[16] | Ciocchetta, Federica; Hillston, Jane, Bio-PEPA: a framework for the modelling and analysis of biological systems, Theor. Comput. Sci., 410, 33, 3065-3084 (2009) · Zbl 1173.68041 |

[17] | Darling, R. W.R., Fluid limits of pure jump Markov processes: a practical guide (October 2002), arXiv e-print |

[18] | Darling, R. W.R.; Norris, J. R., Differential equation approximations for Markov chains, Probab. Surv., 5, 37-79 (2008) · Zbl 1189.60152 |

[19] | De Nicola, Rocco; Latella, Diego; Loreti, Michele; Massink, Mieke, A uniform definition of stochastic process calculi, ACM Comput. Surv., 46, 1, 5 (2013) · Zbl 1288.68184 |

[20] | De Nicola, Rocco; Loreti, Michele; Pugliese, Rosario; Tiezzi, Francesco, A formal approach to autonomic systems programming: the SCEL language, ACM Trans. Auton. Adapt. Syst., 9, 2, 7 (2014) |

[21] | Denby, B.; Le Hègarat-Mascle, S., Swarm intelligence in optimisation problems, Proceedings of the VIII International Workshop on Advanced Computing and Analysis Techniques in Physics Research. Proceedings of the VIII International Workshop on Advanced Computing and Analysis Techniques in Physics Research, Nucl. Instrum. Methods Phys. Res., Sect. A, Accel. Spectrom. Detect. Assoc. Equip., 502, 2, 364-368 (2003) |

[22] | Feng, Cheng; Hillston, Jane, PALOMA: a process algebra for located markovian agents, (Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Florence, Italy, September 8-10, 2014. Proceedings. Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Florence, Italy, September 8-10, 2014. Proceedings, LNCS, vol. 8657 (2014), Springer), 265-280 |

[23] | Fernandez-Marquez, Jose Luis; Di Marzo Serugendo, Giovanna; Montagna, Sara; Viroli, Mirko; Arcos, Josep Lluís, Description and composition of bio-inspired design patterns: a complete overview, Nat. Comput., 12, 1, 43-67 (2013) |

[24] | Gavidia, Daniela; Voulgaris, Spyros; Van Steen, Maarten, A gossip-based distributed news service for wireless mesh networks, (WONS 2006: Third Annual Conference on Wireless On-demand Network Systems and Services. WONS 2006: Third Annual Conference on Wireless On-demand Network Systems and Services, Les Ménuires (France) (January 2006), INRIA, INSA Lyon, Alcatel, IFIP), 59-67 |

[25] | Hillston, J., Fluid flow approximation of pepa models, (2nd International Conference on the Quantitative Evaluation of Systems (2005), IEEE), 33-42 |

[26] | Hillston, Jane, A Compositional Approach to Performance Modelling (1995), CUP · Zbl 0861.90121 |

[27] | Hillston, Jane; Loreti, Michele, CARMA eclipse plug-in: a tool supporting design and analysis of collective adaptive systems, (Quantitative Evaluation of Systems - 13th International Conference, QEST 2016, Quebec City, QC, Canada, August 23-25, 2016, Proceedings. Quantitative Evaluation of Systems - 13th International Conference, QEST 2016, Quebec City, QC, Canada, August 23-25, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9826 (2016), Springer), 167-171 |

[28] | Khadivi, Alireza; Hasler, Martin, Fire detection and localization using wireless sensor networks, (Sensor Applications, Experimentation, and Logistics - First International Conference, SENSAPPEAL 2009, Athens, Greece, September 25, 2009, Revised Selected Papers. Sensor Applications, Experimentation, and Logistics - First International Conference, SENSAPPEAL 2009, Athens, Greece, September 25, 2009, Revised Selected Papers, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 29 (2010), Springer), 16-26 |

[29] | Latella, Diego; Loreti, Michele; Massink, Mieke, Flyfast: a mean field model checker, (Legay, Axel; Margaria, Tiziana, Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS. Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS, Lecture Notes in Computer Science, vol. 10206 (2017)), 303-309 |

[30] | Prasad, K. V.S., A calculus of broadcasting systems, Selected Papers of ESOP’94, the 5th European Symposium on Programming. Selected Papers of ESOP’94, the 5th European Symposium on Programming, Sci. Comput. Program., 25, 2-3, 285-327 (1995) |

[31] | Priami, Corrado, Stochastic π-calculus, Comput. J., 38, 7, 578-589 (1995) |

[32] | Schnoerr, David; Sanguinetti, Guido; Grima, Ramon, Approximation and inference methods for stochastic biochemical kinetics-a tutorial review, J. Phys. A, Math. Theor., 50, 9, Article 093001 pp. (March 2017) |

[33] | Talcott, Carolyn L.; Nigam, Vivek; Arbab, Farhad; Kappé, Tobias, Formal specification and analysis of robust adaptive distributed cyber-physical systems, (Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems - 16th International School on Formal Methods for the Design of Computer, Communication, and Software Systems, SFM 2016, Bertinoro, Italy, June 20-24, 2016, Advanced Lectures. Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems - 16th International School on Formal Methods for the Design of Computer, Communication, and Software Systems, SFM 2016, Bertinoro, Italy, June 20-24, 2016, Advanced Lectures, Lecture Notes in Computer Science (2016), Springer), 1-35 |

[34] | Tschaikowski, Max; Tribastone, Mirco, Spatial fluid limits for stochastic mobile networks, Perform. Eval., 109, 52-76 (2017) · Zbl 1369.90053 |

[35] | Vrba, Pavel; Marík, Vladimír; Siano, Pierluigi; Leitão, Paulo; Zhabelova, Gulnara; Vyatkin, Valeriy; Strasser, Thomas I., A review of agent and service-oriented concepts applied to intelligent energy systems, IEEE Trans. Ind. Inform., 10, 3, 1890-1903 (2014) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.