APICe » Publications » BravettiEntcs124

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

Mario Bravetti, Roberto Gorrieri, Roberto Lucchi, Gianluigi Zavattaro
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.
Keywords: priority
Electronic Notes in Theoretical Computer Science 128(5), pages 39-53, 2005, Elsevier Science B.V.
Proceedings of the 2nd International Workshop on Security Issues in Coordination Models, Languages, and Systems (SecCo 2004), Security Issues in Coordination Models, Languages, and Systems 2004
@article{bravetti-entcs124,
	Author = {Bravetti, Mario and Gorrieri, Roberto and Lucchi, Roberto and Zavattaro, Gianluigi},
	Doi = {10.1016/j.entcs.2004.11.041},
	Issn = {1571-0661},
	Journal = {Electronic Notes in Theoretical Computer Science},
	Keywords = {priority},
	Note = {Proceedings of the 2nd International Workshop on Security Issues in Coordination Models, Languages, and Systems (SecCo 2004), Security Issues in Coordination Models, Languages, and Systems 2004},
	Number = 5,
	Pages = {39--53},
	Publisher = {Elsevier Science B.V.}, 
	Title = {On the Expressiveness of Probabilistic and Prioritized Data-retrieval in {L}inda},
	Url = {http://www.sciencedirect.com/science/article/pii/S1571066105001970},
	Volume = 128,
	Year = 2005}