zbMATH — the first resource for mathematics

On the expressiveness of Linda coordination primitives. (English) Zbl 1046.68616
Summary: We introduce a process algebra containing the coordination primitives of Linda (asynchronous communication via a shared data space, read operation, nonblocking test operators on the shared space). We compare two possible semantics for the output operation: the former, that we call ordered, defines the output as an operation that returns when the message has reached the shared data space; the latter, that we call unordered, returns just after sending the message to the tuple space. The process algebra under the ordered semantics is Turing powerful, as we are able to program any random access machine. The main result of the paper is that the process algebra under the unordered semantics is not Turing powerful. This result is achieved by resorting to a net semantics in terms of contextual nets (P/T nets with inhibitor and read arcs) and by showing that there exists a deadlock-preserving simulation of such nets by finite P/T nets, a formalism where termination is decidable.

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI
[1] Amadio, R.; Castellani, I.; Sangiorgi, D., On bisimulations for the asynchronous π-calculus, Theoret. comput. sci., 195, 291-324, (1998) · Zbl 0915.68009
[2] Boudol, G., Technical report, (1992)
[3] Brogi, A.; Ciancarini, P., The concurrent language shared prolog, ACM trans. programming lang. systems, 13, 99-123, (1991)
[4] Busi, N., Petri nets with inhibitor and Read arcs: semantics, analysis and application to process calculi, (1998), University of SienaDepartment of Mathematics
[5] Busi, N.; Gorrieri, R., A Petri net semantics for π-calculus, Concur’95, Lncs, 962, (1995), p. 145-159
[6] Busi, N.; Gorrieri, R.; Zavattaro, G., Technical report, (1997)
[7] Busi, N.; Gorrieri, R.; Zavattaro, G., Three semantics of the output operation for generative communication, Coordination ’97, Lncs, 1282, (1997), p. 205-219
[8] Busi, N.; Gorrieri, R.; Zavattaro, G., A process algebraic view of linda coordination primitives, Theoret. comput. sci., 192, 167-199, (1998) · Zbl 0895.68016
[9] Busi, N.; Gorrieri, R.; Zavattaro, G., On the Turing equivalence of linda coordination primitives, Express’97, Electronic notes in theoretical computer science, 7, (1997), Elsevier Amsterdam · Zbl 0911.68139
[10] Busi, N.; Pinna, G.M., A causal semantics for contextual P/T nets, Proc. ICTCS ’95, (1995), World Scientific Singapore, p. 311-325
[11] Carriero, N., Research report, (1987)
[12] Carriero, N.; Gelernter, D., How to write parallel programs: A guide to the perplexed, ACM comput. surveys, 21, 323-357, (1989)
[13] Carriero, N.; Gelernter, D., How to write parallel programs: A first course, (1990), MIT Press Cambridge
[14] Carriero, N.; Gelernter, D.; Zuck, L., Bauhaus linda, Onject-based models and languages for concurrent systems, Lncs, 924, (1995), Springer-Verlag New York/Berlin, p. 66-76
[15] Cheng, A.; Esparza, J.; Palsberg, J., Complexity results for 1-safe nets, Theoret. comput. sci., 147, 117-136, (1995) · Zbl 0873.68146
[16] Ciancarini, P.; Jensen, K.K.; Yankelevich, D., On the operational semantics of a coordination language, Object-based models and languages for concurrent systems, Lncs, 924, (1994), Springer-Verlag New York/Berlin, p. 77-106
[17] Douglas, A.; Wood, A.; Rowstron, A., Linda implementation revisited, Transputer and Occam developments, (1995), IOS Press Burke, p. 125-138
[18] Gelernter, D., Generative communication in linda, ACM trans. programming lang. systems, 7, 80-112, (1985) · Zbl 0559.68030
[19] Gelernter, D.; Carriero, N., Coordination languages and their significance, Comm. ACM, 35, 97-107, (1992)
[20] Goltz, U., CCS and Petri nets, Lncs, 469, (1990), Springer-Verlag Berlin, p. 334-357
[21] Groote, J.F., Transition system specifications with negative premises, Theoret. comput. sci., 118, 263-299, (1993) · Zbl 0778.68057
[22] Honda, K.; Tokoro, M., An object calculus for asynchronous communication, Ecoop ’91, Lncs, 512, (1991), Springer-Verlag Berlin, p. 133-147
[23] Jagannathan, S., Technical report, (1990)
[24] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs · Zbl 0683.68008
[25] Milner, R., The polyadic π-calculus: A tutorial technical report, (1991), University of EdinburghDepartment of Computer Science
[26] Milner, R.; Sangiorgi, D., Barbed bisimulation, ICALP’92, (1992), Springer-Verlag Berlin, p. 685-695
[27] Minsky, M.L., Computation: finite and infinite machines, (1967), Prentice-Hall Englewood Cliffs · Zbl 0195.02402
[28] Montanari, U.; Rossi, F., Contextual nets, Acta inform., 32, 545-596, (1995) · Zbl 0835.68084
[29] Narem, J.E., Technical report, (1989)
[30] Reutenauer, C., The mathematics of Petri nets, (1988), Masson Paris
[31] Linda: User’s guide and reference manual, Scientific computing associates, (1995)
[32] Shepherdson, J.C.; Sturgis, J.E., Computability of recursive functions, J. assoc. comput. Mach., 10, 217-255, (1963) · Zbl 0118.25401
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.