On the Expressiveness of Probabilistic and Prioritized Data-retrieval in Linda

Linda tuple-spaces coordination model does not allow to express a preference of tuples. In many applications we could be interested in indicating tuples that should be returned more frequently w.r.t. other ones, or even tuples with a low relevance that should be taken under consideration only if there is no tuple with a higher importance. We present an extension of the tuple-space model with quantitative information that permit to express such forms of preference. More precisely, we consider tuples decorated with a quantitative label. Such labels will be considered with two different semantics, one modeling probabilistic distribution of data retrieval and the other modeling priorities of tuples. Finally, we report all the results concerning the expressiveness gap between the standard model and the proposed extensions. We show that by adding probabilities the leader election problem can be solved. More surprisingly, the addition of priorities makes the model Turing complete, while we prove that this is not the case for the other two calculi.