On the introduction of density in tuple-space coordination languages

Coordination languages have been proved very suitable for modeling and programming service-oriented applications. In particular, those based on tuple spaces offer an elegant way of making different components of such applications interact smoothly through the deposit and retrieval of tuples in a shared space. However, in their basic form, these languages only allow one tuple to be put at a time and, when more than one tuple matches a required one, the selection is made non-deterministically. This is obviously too weak to capture popularity or quality measures, which are nevertheless central in service-oriented applications. To that end, we propose an extension of a Linda-like language aiming at promoting the notion of density and, based on De Boer and Palamidessi's notion of modular embedding, study its expressiveness. We prove accordingly that it strictly increases the expressiveness of Linda while keeping the same implementation efficiency. We also compare it with languages based on multiset rewriting, such as Gamma, and establish that, although it is less expressive, it benefits from a much more efficient scheme. Finally we study the hierarchy of the sublanguages induced by considering subsets of tuple primitives and prove that it follows that of the Linda family of languages.