Probabilistic and Prioritized Data Retrieval in the Linda Coordination Model

Linda tuple spaces are flat and unstructured, in the sense that they do not allow for expressing preferences of tuples; for example, 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. In this paper we investigate, in a process algebraic setting, how probabilities and priorities can be introduced in the Linda coordination model in order to support a more sophisticated data retrieval mechanism. As far as probabilities are concerned, we show that the Linda pattern-matching data retrieval makes it necessary to deal with weights instead of just pure probabilities, as instead can be done in standard process algebras. Regarding priorities, we present two possible ways for adding them to Linda; in the first one the order of priorities is statically fixed, in the second one it is dynamically instantiated when a data-retrieval operation is executed.