×

On the expressive power of Klaim-based calculi. (English) Zbl 1092.68070

Summary: We study the expressive power of variants of Klaim, an experimental language with programming primitives for network-aware programming that combines the process algebra approach with the coordination-oriented one. Klaim has proved to be suitable for programming a wide range of distributed applications with agents and code mobility, and has been implemented on the top of a runtime system written in Java. In this paper, the expressivity of its constructs is tested by distilling from it a few, more and more foundational, languages and by studying the encoding of each of them into a simpler one. The expressive power of the considered calculi is finally tested by comparing one of them with asynchronous \(\pi\)-calculus.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68N15 Theory of programming languages

Software:

Linda; tKlaim; Klava; KLAIM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amadio, R. M.; Castellani, I.; Sangiorgi, D., On bisimulations for the asynchronous \(\pi \)-calculus, Theoret. Comput. Sci., 195, 2, 291-324 (1998) · Zbl 0915.68009
[2] Bettini, L.; De Nicola, R.; Ferrari, G.; Pugliese, R., Interactive mobile agents in X-KLAIM, (Proc. Seventh WETICE. Proc. Seventh WETICE, IEEE Computer Society, Silver Spring, MD (1998)), 110-115
[3] Bettini, L.; De Nicola, R.; Pugliese, R., KLAVA: a java package for distributed and mobile applications, Software—Practice Experience, 32, 1365-1394 (2002) · Zbl 1009.68933
[4] Bettini, L.; Nicola, R. D., Mobile distributed programming in x-Klaim, (Bernardo, M.; Bogliolo, A., SFM, Lecture Notes in Computer Science, Vol. 3465 (2005), Springer: Springer Berlin), 29-68
[5] Boreale, M., On the expressiveness of internal mobility in name-passing calculi, Theoret. Comput. Sci., 195, 2, 205-226 (1998) · Zbl 0915.68059
[6] G. Boudol, Asynchrony and the \(\operatorname{\Pi;} \); G. Boudol, Asynchrony and the \(\operatorname{\Pi;} \)
[7] Busi, N.; Gorrieri, R.; Zavattaro, G., Comparing three semantics for linda-like languages, Theoret. Comput. Sci., 240, 1, 49-90 (2000) · Zbl 0954.68092
[8] Busi, N.; Gorrieri, R.; Zavattaro, G., On the expressiveness of linda coordination primitives, Inform. and Comput., 156, 1-2, 90-121 (2000) · Zbl 1046.68616
[9] Cacciagrano, D.; Corradini, F., On synchronous and asynchronous communication paradigms, (Proc. ICTCS’01, Lecture Notes in Computer Science, Vol. 2202 (2001), Springer: Springer Berlin), 256-268 · Zbl 1042.68614
[10] Cardelli, L.; Gordon, A. D., Mobile ambients, Theoret. Comput. Sci., 240, 1, 177-213 (2000) · Zbl 0954.68108
[11] De Nicola, R.; Ferrari, G.; Pugliese, R., KLAIM: a kernel language for agents interaction and mobility, IEEE Trans. Software Eng., 24, 5, 315-330 (1998)
[12] De Nicola, R.; Ferrari, G.; Pugliese, R., Programming access control: the Klaim experience, (Proc. CONCUR’00, Lecture Notes in Computer Science, Vol. 1877 (2000), Springer: Springer Berlin), 48-65 · Zbl 0999.68557
[13] R. De Nicola, D. Gorla, R. Pugliese, On the expressive power of KLAIM-based calculi, in: Proc. EXPRESS’04, ENTCS, Vol. 128, No. 2, Elsevier, Amsterdam, 2004, pp. 117-130.; R. De Nicola, D. Gorla, R. Pugliese, On the expressive power of KLAIM-based calculi, in: Proc. EXPRESS’04, ENTCS, Vol. 128, No. 2, Elsevier, Amsterdam, 2004, pp. 117-130. · Zbl 1272.68298
[14] R. De Nicola, D. Gorla, R. Pugliese, Basic observables for a calculus for global computing, Proc. ICALP’05, Vol. 3580, Springer, 2005, pp. 1226-1238.; R. De Nicola, D. Gorla, R. Pugliese, Basic observables for a calculus for global computing, Proc. ICALP’05, Vol. 3580, Springer, 2005, pp. 1226-1238. · Zbl 1085.68098
[15] De Nicola, R.; Gorla, D.; Pugliese, R., Global computing in a dynamic network of tuple spaces, (Proc. COORDINATION’05, Lecture Notes in Computer Science, Vol. 3454 (2005), Springer), 157-172
[16] De Nicola, R.; Gorla, D.; Pugliese, R., Pattern matching over a dynamic network of tuple spaces, (Proc. FMOODS’05, Lecture Notes in Computer Science, Vol. 3535 (2005), Springer: Springer Berlin), 1-14 · Zbl 1461.68131
[17] Gelernter, D., Generative communication in linda, ACM Trans. Programming Languages Systems, 7, 1, 80-112 (1985) · Zbl 0559.68030
[18] D. Gorla, Semantic Approaches to global computing systems, Ph.D. Thesis, Dip. Sistemi ed Informatica, Univ. di Firenze, 2005.; D. Gorla, Semantic Approaches to global computing systems, Ph.D. Thesis, Dip. Sistemi ed Informatica, Univ. di Firenze, 2005.
[19] Gorla, D.; Pugliese, R., Resource access and mobility control with dynamic privileges acquisition, (Proc. ICALP’03, Lecture Notes in Computer Science, Vol. 2719 (2003), Springer: Springer Berlin), 119-132 · Zbl 1039.68542
[20] Hennessy, M.; Riely, J., Resource access control in systems of mobile agents, Inform. and Comput., 173, 82-120 (2002) · Zbl 1009.68081
[21] Honda, K.; Tokoro, M., An object calculus for asynchronous communication, (Proc. ECOOP’91, Lecture Notes in Computer Science, Vol. 512 (1991), Springer: Springer Berlin), 133-147
[22] Milner, R., The polyadic \(\pi \)-calculus: a tutorial, (Logic and Algebra of Specification, Series F. NATO ASI, Vol. 94 (1993), Springer: Springer Berlin)
[23] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, part I/II, Inform. and Comput., 100, 1-77 (1992)
[24] Nestmann, U., What is a ‘good’ encoding of guarded choice?, Inform. and Comput., 156, 287-319 (2000) · Zbl 1046.68625
[25] Nestmann, U.; Pierce, B. C., Decoding choice encodings, Inform. and Comput., 163, 1-59 (2000) · Zbl 1003.68080
[26] Palamidessi, C., Comparing the expressive power of the synchronous and the asynchronous \(\pi \)-calculi, Math. Struct. Comput. Sci., 13, 5, 685-719 (2003)
[27] Parrow, J., An introduction to the pi-calculus, (Handbook of Process Algebra (2001), Elsevier: Elsevier Amsterdam), 479-543 · Zbl 1035.68071
[28] Riely, J.; Hennessy, M., Trust and partial typing in open systems of mobile agents, (Proc. POPL ’99 (1999), ACM: ACM New York), 93-104
[29] Sangiorgi, D., Bisimulation in higher-order process calculi, Inform. and Comput., 131, 141-178 (1996) · Zbl 0876.68042
[30] D. Sangiorgi, D. Walker, The \(\operatorname{\Pi;} \); D. Sangiorgi, D. Walker, The \(\operatorname{\Pi;} \) · Zbl 0981.68116
[31] Yoshida, N., Graph types for monadic mobile processes, (Proc. FST-TCS’96, Lecture Notes in Computer Science, Vol. 1180 (1996), Springer: Springer Berlin), 371-386
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.