×

zbMATH — the first resource for mathematics

On the expressiveness of multiplicities in data-based coordination languages. (English) Zbl 1433.68076
Summary: Coordination languages and models have proved to be well suited to program the interaction of a wide variety of data-intensive distributed systems. Building upon previous work by the authors, this paper aims at exploring how the addition of multiplicity information to tuples increases the expressiveness of Linda-like languages. It proposes a set of languages integrating the multiplicity in different perspectives. The expressiveness hierarchy between these languages is then studied through the notion of modular embedding proposed by De Boer and Palamidessi. Complementing these theoretical study, considerations on the implementation are drawn, which attest that the more expressive a language is, the more expensive is its implementation.
MSC:
68N15 Theory of programming languages
68M14 Distributed systems
Software:
Linda
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bravetti, M.; Zavattaro, G., Service oriented computing from a process algebraic perspective, J. Log. Algebraic Program., 70, 1, 3-14 (2007) · Zbl 1178.68072
[2] Jongmans, S.-S.; Santini, F.; Sargolzaei, M.; Arbab, F.; Afsarmanesh, H., Automatic code generation for the orchestration of Web services with Reo, (Paoli, F. D.; Pimentel, E.; Zavattaro, G., Proceedings of the First European Conference on Service-Oriented and Cloud Computing. Proceedings of the First European Conference on Service-Oriented and Cloud Computing, Lecture Notes in Computer Science, vol. 7592 (2012), Springer), 1-16
[3] Tolksdorf, R., Laura - a service-based coordination language, Sci. Comput. Program., 31, 2-3, 359-381 (1998) · Zbl 0941.68015
[4] Mariani, S., Coordination of Complex Sociotechnical Systems - Self-Organisation of Knowledge in MoK, Artificial Intelligence: Foundations, Theory, and Algorithms (2016), Springer
[5] Gelernter, D., Generative communication in Linda, ACM Trans. Program. Lang. Syst., 7, 1, 80-112 (1985) · Zbl 0559.68030
[6] Jacquet, J.-M.; Linden, I.; Darquennes, D., On density in coordination languages, (Canal, C.; Villari, M., Proceedings of the European Conference on Service Oriented and Cloud Computing 2013. Proceedings of the European Conference on Service Oriented and Cloud Computing 2013, Communications in Computer and Information Science, vol. 393 (2013), Springer), 189-203
[7] Darquennes, D.; Jacquet, J.-M.; Linden, I., On distributed density in tuple-based coordination languages, (Cámara, J.; Proença, J., Proceedings 13th International Workshop on Foundations of Coordination Languages and Self-Adaptive Systems. Proceedings 13th International Workshop on Foundations of Coordination Languages and Self-Adaptive Systems, EPTCS, vol. 175 (2015), Springer), 36-53
[8] Brogi, A.; Jacquet, J.-M., Modeling coordination via asynchronous communication, (Garlan, D.; Le Métayer, D., Proceedings of the Second International Conference on Coordination Languages and Models. Proceedings of the Second International Conference on Coordination Languages and Models, Berlin, Germany. Proceedings of the Second International Conference on Coordination Languages and Models. Proceedings of the Second International Conference on Coordination Languages and Models, Berlin, Germany, Lecture Notes in Computer Science, vol. 1282 (1997)), 238-255
[9] Brogi, A.; Jacquet, J.-M., On the expressiveness of coordination via shared dataspaces, Sci. Comput. Program., 46, 1-2, 71-98 (2003) · Zbl 1032.68038
[10] Brogi, A.; Jacquet, J.-M.; Linden, I., On modeling coordination via asynchronous communication and enhanced matching, Electron. Notes Theor. Comput. Sci., 68, 3 (2003)
[11] Linden, I.; Jacquet, J.-M.; Bosschere, K. D.; Brogi, A., On the expressiveness of timed coordination models, Sci. Comput. Program., 61, 2, 152-187 (2006)
[12] Banâtre, J.-P.; Le Métayer, D., Programming by multiset transformation, Commun. ACM, 36, 1, 98-111 (1993)
[13] Banâtre, J.-P.; Métayer, D. L., Gamma and the Chemical Reaction Model: Ten Years After, Coordination Programming, 3-41 (1996), Imperial College Press: Imperial College Press London
[14] Darquennes, D.; Jacquet, J.-M.; Linden, I., On multiplicities in tuple-based coordination languages: the Bach family of languages and its expressiveness study, (Serugendo, G. D.M.; Loreti, M., Proceedings of the 20th International Conference on Coordination Models and Languages. Proceedings of the 20th International Conference on Coordination Models and Languages, Lecture Notes in Computer Science, vol. 10852 (2018), Springer), 81-109
[15] Jacquet, J.-M.; Linden, I., Coordinating context-aware applications in mobile ad-hoc networks, (Braun, T.; Konstantas, D.; Mascolo, S.; Wulff, M., Proceedings of the First ERCIM Workshop on eMobility (2007), The University of Bern), 107-118
[16] Groote, J.; Mousavi, M., Modeling and Analysis of Communicating Systems (2014), MIT Press
[17] Brogi, A.; Jacquet, J.-M., On the expressiveness of coordination models, (Ciancarini, C.; Wolf, A., Proceedings of the Third International Conference on Coordination Languages and Models. Proceedings of the Third International Conference on Coordination Languages and Models, Lecture Notes in Computer Science, vol. 1594 (Apr 1999), Springer-Verlag), 134-149
[18] Linden, I.; Jacquet, J.-M., On the expressiveness of absolute-time coordination languages, (Nicola, R. D.; Ferrari, G.; Meredith, G., Proc. 6th International Conference on Coordination Models and Languages. Proc. 6th International Conference on Coordination Models and Languages, Lecture Notes in Computer Science, vol. 2949 (2004), Springer), 232-247
[19] Linden, I.; Jacquet, J.-M., On the expressiveness of timed coordination via shared dataspaces, Electron. Notes Theor. Comput. Sci., 180, 2, 71-89 (2007)
[20] Linden, I.; Jacquet, J.-M.; Bosschere, K. D.; Brogi, A., On the expressiveness of relative-timed coordination models, Electron. Notes Theor. Comput. Sci., 97, 125-153 (2004)
[21] Omicini, A., Formal ReSpecT in the A&A perspective, Electron. Notes Theor. Comput. Sci., 175, 2, 97-117 (2007)
[22] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley · Zbl 0426.68001
[23] Shapiro, E., Embeddings among concurrent programming languages, (Cleaveland, W., Proceedings of Concur 1992. Proceedings of Concur 1992, Lecture Notes in Computer Science (1992), Springer), 486-503
[24] de Boer, F.; Palamidessi, C., Embedding as a tool for language comparison, Inf. Comput., 108, 1, 128-157 (1994)
[25] Brogi, A.; Jacquet, J.-M., On the expressiveness of Linda-like concurrent languages, Electron. Notes Theor. Comput. Sci., 16, 2, 61-82 (1998)
[26] Jacquet, J.-M.; Linden, I.; Darquennes, D., On the introduction of density in tuple-space coordination languages, Sci. Comput. Program., 115-116, 149-176 (2016)
[27] Brogi, A.; Jacquet, J.-M., On the expressiveness of Linda-like concurrent languages, Electron. Notes Theor. Comput. Sci., 16, 2, 61-82 (1998)
[28] Bosschere, K. D.; Jacquet, J.-M., Multi-prolog: definition, operational semantics, and implementation, (Warren, D., Proceedings of the International Conference on Logic Programming (1993), The MIT Press: The MIT Press Budapest, Hongrie), 299-314
[29] Jacquet, J.-M.; Linden, I.; Staicu, M.-O., Blackboard rules: from a declarative reading to its application for coordinating context-aware applications in mobile ad hoc networks, Sci. Comput. Program., 115-116, 79-99 (2016)
[30] Zavattaro, G., On the incomparability of Gamma and Linda, Electron. Trans. Numer. Anal. (1998)
[31] Zavattaro, G., Towards a hierarchy of negative test operators for generative communication, Electron. Notes Theor. Comput. Sci., 16, 154-170 (1998)
[32] Bonsangue, M. M.; Kok, J. N.; Zavattaro, G., Comparing coordination models based on shared distributed replicated data, (ACM Symposium on Applied Computing (1999)), 156-165
[33] Busi, N.; Gorrieri, R.; Zavattaro, G., A process algebraic view of Linda coordination primitives, Theor. Comput. Sci., 192, 167-199 (1998)
[34] Busi, N.; Gorrieri, R.; Zavattaro, G., On the Turing equivalence of Linda coordination primitives, Electron. Notes Theor. Comput. Sci., 7, 75 (1997)
[35] Bravetti, M.; Gorrieri, R.; Lucchi, R.; Zavattaro, G., Quantitative information in the tuple space coordination model, Theor. Comput. Sci., 346, 1, 28-57 (2005)
[36] Bravetti, M.; Gorrieri, R.; Lucchi, R.; Zavattaro, G., Probabilistic and prioritized data retrieval in the Linda coordination model, (De Nicola, R.; Ferrari, G.; Meredith, G., Proceedings of the 6th International Conference on Coordination Models and Languages. Proceedings of the 6th International Conference on Coordination Models and Languages, Lecture Notes in Computer Science, vol. 2949 (2004), Springer), 55-70
[37] Viroli, M.; Casadei, M., Biochemical tuple spaces for self-organising coordination, (Field, J.; Vasconcelos, V. T., Proceedings of 11th International Conference on Coordination Models and Languages. Proceedings of 11th International Conference on Coordination Models and Languages, Lecture Notes in Computer Science, vol. 5521 (2009), Springer), 143-162
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.