×

zbMATH — the first resource for mathematics

A calculus for collective-adaptive systems and its behavioural theory. (English) Zbl 1430.68158
Summary: We propose a process calculus, named AbC, to study the behavioural theory of interactions in collective-adaptive systems by relying on attribute-based communication. An AbC system consists of a set of parallel components each of which is equipped with a set of attributes. Communication takes place in an implicit multicast fashion, and interaction among components is dynamically established by taking into account “connections” as determined by predicates over their attributes. The structural operational semantics of AbC is based on Labelled Transition Systems that are also used to define bisimilarity between components. Labelled bisimilarity is in full agreement with a barbed congruence, defined by relying on simple basic observables and context closure. The introduced equivalence is used to study the expressiveness of AbC in terms of encoding aspects of broadcast channel-based interactions and to establish formal relationships between system descriptions at different levels of abstraction.

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q55 Semantics in the theory of computing
Software:
CC-Pi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ferscha, A., Collective adaptive systems, (Adjunct Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2015 ACM International Symposium on Wearable Computers, (2015), ACM), 893-895
[2] Sommerville, I.; Cliff, D.; Calinescu, R.; Keen, J.; Kelly, T.; Kwiatkowska, M.; Mcdermid, J.; Paige, R., Large-scale complex it systems, Commun. ACM, 55, 7, 71-77, (2012)
[3] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, ii, Inf. Comput., 100, 1, 41-77, (1992) · Zbl 0752.68037
[4] Prasad, K., A calculus of broadcasting systems, (TAPSOFT’91, (1991), Springer), 338-358
[5] Bengtson, J.; Johansson, M.; Parrow, J.; Victor, B., Psi-calculi: a framework for mobile processes with nominal data and logic, Log. Methods Comput. Sci., 7, 1, (2011) · Zbl 1213.68399
[6] Wischik, L.; Gardner, P., Explicit fusions, Theor. Comput. Sci., 340, 3, 606-630, (2005) · Zbl 1077.68066
[7] Saraswat, V. A.; Rinard, M. C., Concurrent constraint programming, (Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages. Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, San Francisco, California, USA, January 1990, (1990)), 232-245
[8] Gilbert, D. R.; Palamidessi, C., Concurrent constraint programming with process mobility, (Computational Logic - CL 2000, Proceedings of the First International Conference. Computational Logic - CL 2000, Proceedings of the First International Conference, London, UK, 24-28 July, 2000, (2000)), 463-477 · Zbl 0983.68617
[9] Buscemi, M. G.; Montanari, U., Cc-pi: a constraint-based language for specifying service level agreements, (Programming Languages and Systems, Proceedings of the 16th European Symposium on Programming, ESOP 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software. Programming Languages and Systems, Proceedings of the 16th European Symposium on Programming, ESOP 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24 - April 1, 2007, (2007)), 18-32 · Zbl 1187.68063
[10] Agha, G., Actors: A Model of Concurrent Computation in Distributed Systems, (1986), MIT Press: MIT Press Cambridge, MA, USA
[11] Ene, C.; Muntean, T., A broadcast-based calculus for communicating systems, (Parallel and Distributed Processing Symposium, International, vol. 3, (2001), IEEE Computer Society), 30149b
[12] Alrahman, Y. A.; De Nicola, R.; Loreti, M., On the power of attribute-based communication, (Formal Techniques for Distributed Objects, Components, and Systems - 36th IFIP International Conference, FORTE, (2016), Springer), 1-18, full technical report can be found on · Zbl 1347.68022
[13] Alrahman, Y. A.; De Nicola, R.; Loreti, M., Programming the interactions of collective adaptive systems by relying on attribute-based communication, e-prints
[14] Angluin, D.; Aspnes, J.; Diamadi, Z.; Fischer, M. J.; Peralta, R., Computation in networks of passively mobile finite-state sensors, Distrib. Comput., 18, 4, 235-253, (2006) · Zbl 1266.68042
[15] Boreale, M.; De Nicola, R.; Pugliese, R., Basic observables for processes, Inf. Comput., 149, 1, 77-98, (1999) · Zbl 0928.68013
[16] Milner, R.; Sangiorgi, D., Barbed bisimulation, (Automata, Languages and Programming, (1992), Springer), 685-695
[17] Honda, K.; Yoshida, N., On reduction-based process semantics, Theor. Comput. Sci., 151, 2, 437-486, (1995) · Zbl 0871.68122
[18] Sangiorgi, D.; Walker, D., The pi-Calculus: A Theory of Mobile Processes, (2003), Cambridge University Press
[19] Milner, R., Communication and Concurrency, (1989), Prentice-Hall, Inc. · Zbl 0683.68008
[20] Milner, R., A Calculus of Communicating Systems, (1980), Springer · Zbl 0452.68027
[21] Borgström, J.; Huang, S.; Johansson, M.; Raabjerg, P.; Victor, B.; Pohjola, J.Å.; Parrow, J., Broadcast psi-calculi with an application to wireless protocols, Softw. Syst. Model., 14, 1, 201-216, (2015)
[22] Agha, G.; Callsen, C. J., ActorSpace: An Open Distributed Programming Paradigm, vol. 28, (1993), ACM
[23] Chockler, G. V.; Keidar, I.; Vitenberg, R., Group communication specifications: a comprehensive study, ACM Comput. (CSUR), 33, 4, 427-469, (2001)
[24] Holbrook, H. W.; Cheriton, D. R., Ip multicast channels: express support for large-scale single-source applications, ACM SIGCOMM Computer Communication Review, 29, 65-78, (1999)
[25] M.A. Bass, F.T. Nguyen, Unified publish and subscribe paradigm for local and remote publishing destinations, US Patent 6,405,266 (Jun. 11 2002).
[26] Eugster, P. T.; Felber, P. A.; Guerraoui, R.; Kermarrec, A.-M., The many faces of publish/subscribe, ACM Comput. Surv., 35, 2, 114-131, (2003)
[27] Given-Wilson, T., Expressiveness via intensionality and concurrency, (Theoretical Aspects of Computing - ICTAC 2014 - Proceedings of the 11th International Colloquium. Theoretical Aspects of Computing - ICTAC 2014 - Proceedings of the 11th International Colloquium, Bucharest, Romania, September 17-19, 2014, (2014)), 206-223 · Zbl 1432.68307
[28] Gorla, D., Towards a unified approach to encodability and separation results for process calculi, Inf. Comput., 208, 9, 1031-1053, (2010) · Zbl 1209.68336
[29] Abadi, M.; Blanchet, B.; Fournet, C., The applied pi calculus: mobile values, new names, and secure communication, J. ACM, 65, 1, Article 1 pp., (2018) · Zbl 1426.68037
[30] Alrahman, Y. A.; De Nicola, R.; Garbi, G.; Loreti, M., A distributed coordination infrastructure for attribute-based interaction, (Formal Techniques for Distributed Objects, Components, and Systems - Proceedings of the 38th IFIP WG 6.1 International Conference, FORTE 2018, Held as Part of the 13th International Federated Conference on Distributed Computing Techniques. Formal Techniques for Distributed Objects, Components, and Systems - Proceedings of the 38th IFIP WG 6.1 International Conference, FORTE 2018, Held as Part of the 13th International Federated Conference on Distributed Computing Techniques, DisCoTec 2018, Madrid, Spain, June 18-21, 2018, (2018)), 1-20
[31] Prasad, K. V., A calculus of broadcasting systems, Sci. Comput. Program., 25, 2, 285-327, (1995)
[32] Given-Wilson, T.; Gorla, D.; Jay, B., Concurrent pattern calculus, (Theoretical Computer Science, (2010), Springer), 244-258 · Zbl 1198.68211
[33] John, M.; Lhoussaine, C.; Niehren, J.; Uhrmacher, A. M., The attributed pi-calculus with priorities, (Transactions on Computational Systems Biology XII, (2010), Springer), 13-76 · Zbl 1275.92023
[34] John, M.; Lhoussaine, C.; Niehren, J., Dynamic compartments in the imperative π-calculus, (Computational Methods in Systems Biology, (2009), Springer), 235-250
[35] Bruni, A.; Mödersheim, S.; Nielson, F.; Nielson, H. R., Set-pi: set membership p-calculus, (2015 IEEE 28th Computer Security Foundations Symposium, (2015)), 185-198
[36] Vigo, R.; Nielson, F.; Riis Nielson, H., Broadcast, denial-of-service, and secure communication, (10th International Conference on integrated Formal Methods. 10th International Conference on integrated Formal Methods, iFM’13. 10th International Conference on integrated Formal Methods. 10th International Conference on integrated Formal Methods, iFM’13, LNCS, vol. 7940, (2013)), 410-427
[37] Prasad, K., A calculus of value broadcasts, (PARLE’93 Parallel Architectures and Languages Europe, (1993), Springer), 391-402
[38] Alrahman, Y. A.; Perelli, G.; Piterman, N., A computational framework for adaptive systems and its verification, CoRR
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.