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


Mario Bravetti, Roberto Gorrieri, Roberto Lucchi, Gianluigi Zavattaro

Proceedings of the 2nd International Workshop on Security Issues in Coordination Models, Languages, and Systems (SecCo 2004), pages 39-53
Electronic Notes in Theoretical Computer Science 128(5),  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

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
 @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

Tags:

Publication

— authors

Mario Bravetti, Roberto Gorrieri, Roberto Lucchi, Gianluigi Zavattaro

— status

published

— sort

paper in proceedings

Venue

— volume

Proceedings of the 2nd International Workshop on Security Issues in Coordination Models, Languages, and Systems (SecCo 2004)

— series

Electronic Notes in Theoretical Computer Science

— volume

128

— issue

5

— pages

39-53

— publication date

2005

URLs

original page

Identifiers

— DOI

10.1016/j.entcs.2004.11.041

— print ISSN

1571-0661

BibTeX

— BibTeX ID
bravetti-entcs124
— BibTeX category
article

Partita IVA: 01131710376 - Copyright © 2008-2022 APICe@DISI Research Group - PRIVACY