Tuple-based Coordination of Stochastic Systems with Uniform Primitives Stefano Mariani Andrea Omicini DISI, A LMA M ATER S TUDIORUM–Università di Bologna DISI, A LMA M ATER S TUDIORUM–Università di Bologna via Sacchi 3, 47521 Cesena, Italy via Sacchi 3, 47521 Cesena, Italy Email: s.mariani@unibo.it Email: andrea.omicini@unibo.it Abstract—Complex computational systems – such as perva- To this end, in this paper we define uniform coordination sive, adaptive, and self-organising ones – typically rely on simple primitives (uin, urd) – first mentioned in [8] – as the special- yet expressive coordination mechanisms: this is why coordination isation of L INDA getter primitives featuring probabilistic non- models and languages can be exploited as the sources of the determinism instead of don’t know non-determinism. Roughly essential abstractions and mechanisms to build such systems. speaking, uniform primitives allow programmers to both spec- While the features of tuple-based models make them well suited ify and (statistically) predict the probability to retrieve one for complex system coordination, they lack the probabilistic mechanisms for modelling the stochastic behaviours typically specific tuple among a bag of matching tuples, thus making it required by adaptivity and self-organisation. possible to statistically control non-deterministic systems. To this end, in this paper we explicitly introduce uniform Accordingly, in this paper we first define uniform prim- primitives as a probabilistic specialisation of standard tuple-based itives based on the probabilistic framework from [9] (Sec- coordination primitives, replacing don’t know non-determinism tion II), then demonstrate their expressive power both formally with uniform distribution. We define their semantics and discuss – by exploiting probabilistic modular embedding [10] – and by their expressiveness and their impact on system predictability. discussing some examples (Section III). Finally, we compare uniform primitives with other approaches in probabilistic and I. I NTRODUCTION stochastic coordination (Section IV). While computational systems grow in complexity, coordi- nation models and technologies are more and more essential to harness the intricacies of intra- and inter-system interaction [1], II. U NIFORM P RIMITIVES [2]. In particular, tuple-based coordination models – derived L INDA getter primitives – that is, data-retrieval primitives from the original L INDA [3] – have shown their power in in and rd – are shared by all tuple-based coordination models, the coordination of pervasive, adaptive, and self-organising and provide them with don’t know non-determinism: when one systems [4], such as SAPERE [5] and MoK [6]. or more tuples in a tuple space match a given template, any A foremost feature of computational models for open, of the matching tuples can be non-deterministically returned. adaptive and self-* systems is non-determinism. L INDA fea- tures don’t know non-determinism in the access to tuples in In a single getter operation, only a point-wise property tuple spaces, handled with a don’t care approach: (i) a tuple affects tuple retrieval: that is, the conformance of a tuple to space is a multiset of tuples where multiple tuples possibly the template, independently of the spatial context—namely, match a given template; (ii) which tuple among the matching the other tuples in the same space. Furthermore, in a sequence ones is actually retrieved by a getter operation (in, rd) can be of getter operations, don’t know non-determinism makes any neither specified nor predicted (don’t know); (iii) nonetheless, prediction of the overall behaviour impossible: e.g., reading the coordinated system is designed so as to keep on working one thousand times the same template in a tuple space with whichever is the matching tuple returned (don’t care). ten matching tuples could possibly lead to retrieving the same tuple all times, or one hundred times each, or whatever The latter assumption requires that when a process uses admissible combination one could think of—no prediction a template matching multiple tuples, which specific tuple is possible, according to the model. Again, then, only a point- actually retrieved is not relevant for that process. This is wise property can be ensured even in time: that is, only the not the case, however, in many of today adaptive and self- mere compliance to the model of each individual operation in organising systems, where processes may need to implement the sequence. stochastic behaviours like “most of the time do this” or “not always do that”—which obviously do not cope well with Instead, uniform primitives enrich tuple-based coordination don’t know non-determinism. For instance, all the nature- models with the ability of performing operations that ensure inspired models and systems emerged in the last decade – global system properties instead of point-wise ones, both such as chemical, biochemical, stigmergic, and field-based – in space and in time. More precisely, uniform primitives are examples of the broad class of self-organising systems that replace don’t know non-determinism with probabilistic non- precisely require such a sort of behaviour [7]—which by no determinism to situate a primitive invocation in space – the means can be enabled by the canonical L INDA model and its tuple actually retrieved depends on the other tuples in the direct derivatives. space – and to predict its behaviour in time — statistically, the distribution of the tuples retrieved will tend to be uniform, Operationally, uniform primitives behave as follows. When over time. executed, a uniform primitive takes a snapshot of the tuple space, “freezing” its state at a certain point in time—and space, Whereas exploiting probabilistic non-determinism to its being a single tuple space the target of basic L INDA primitives. full extent would lead to the definition of the complete set of The snapshot is then exploited to assign a probabilistic value uniform coordination primitives – including, e.g., uinp and pi ∈ [0, 1] to any tuple ti∈{1..n} in the space—where n is the urdp primitives –, here we aim at understanding the fun- total number of tuples in the space. There, non-matching tuples damental mechanisms making tuple-based models well suited have value p = 0, matching tuples have value p = 1/m (where for complex system coordination, by enhancing them with m ≤ n is the number of matching tuples), and the overall sum the probabilistic mechanisms for modelling the stochastic be- P of probability values is i=1..n pi = 1. The choice of the haviours typically required by adaptivity and self-organisation. matching tuple to be returned is then statistically based on the Accordingly, in this paper we focus only on the two uniform computed probabilistic values. primitives (uin, urd) that specialise the basic L INDA getter primitives. In the remainder of this section, first (Subsec- As a consequence, while standard getter primitives exhibit tion II-A) we define them informally, then (Subsection II-B) point-wise properties only, uniform primitives feature global we provide them with a formal semantic specification accord- properties, both in space and time. In terms of spatial con- ing to the probabilistic framework defined in [9]. text, in fact, standard getter primitives can return a matching tuple independently of the other tuples currently in the same space—so, they are “context unaware”. Instead, uniform getter A. Informal semantics primitives return matching tuples based on the overall state of the tuple space—so, their behaviour is context aware. In The main motivation behind uniform primitives is to intro- terms of time, too, sequences of standard getter operations duce a simple yet expressive probabilistic mechanism in tuple- present no meaningful properties. Instead, by definition, se- based coordination: simple enough to work as a specialisation quences of uniform getter operations tend to globally exhibit a of standard L INDA operations, expressive enough to model the uniform distribution over time. So, for instance, performing N most relevant stochastic behaviours of complex computational urd(colour(X)) operations over a tuple space containing systems such as adaptive and self-organising ones. 10 colour(white) and 100 colour(black) tuples, leads to a sequence of returned tuples which, while N grows, Whereas expressiveness is discussed in Section III, simplic- would tend to contain ten times more colour(black) ity is achieved by defining uniform primitives as specialised tuples than colour(white) ones. versions of standard L INDA primitives: so, first of all, uin and urd are compliant with the standard semantics of in and B. Formal semantics rd. In the same way as in and rd, uin and urd ask tuple spaces for one tuple matching a given template, suspend when In order to define the semantics of (getter) uniform prim- no matching tuple is available, return a matching tuple chosen itives, we rely upon a simplified version of the process- non-deterministically when one or more matching tuples are algebraic framework in [9], dropping multi-level priority prob- available in the tuple space. As a straightforward consequence, abilities. In detail, we exploit closure operator ↑, handles h, any tuple-based coordination system working with in and rd and closure term G as follows: would also work by using instead uin and urd, respectively— (i) handles coupled to actions (open transitions) represent and any process using in and rd could adopt uin and urd tuple templates associated with primitives; instead without any further change. (ii) handles listed in closure term G represent tuples On the other hand, the nature of the specialisation lays offered (as synchronisation items) by the tuple space precisely in the way in which a tuple is non-deterministically (modelled as a process); chosen among the (possibly) many tuples matching the tem- plate. While in standard L INDA the choice is performed (iii) closure term G associates handles (tuples) with their based on don’t know non-determinism, uniform primitives cardinality in the tuple space; exploit instead probabilistic non-determinism with uniform (iv) closure operator ↑ (a) matches admissible synchroni- distribution. So, if a standard getter primitive requires a tuple sations between processes and the tuple space, and with template T , and m tuples t1 , .., tm matching T are (b) computes their associated probability distribution in the tuple space when the request is executed, any tuple based upon handle-associated values. ti∈{1..m} could be retrieved, but nothing more could be said— no other assertion is possible about the result of the getter It is worth to note that closure operator ↑ could be seen as operation. Instead, when a uniform getter primitive requires a following our statistical interpretation of a uniform primitive: tuple with template T , and m tuples t1 , .., tm matching T are it takes a snapshot of the tuple space state – matching, step available in the tuple space when the request is served, one (a) – then samples it probabilistically — sampling, step (b). assertion is possible about the result of the getter operation: 1) Semantics of uin (uniform consumption): Three transi- that is, each of the m matching tuples ti∈{1..m} has exactly tion rules define the operational semantics of the uin primitive the same probability 1/m to be returned. So, for instance, for uniform consumption: if 2 colour(blue) and 3 colour(red) tuples occur in the tuple space when a urd(colour(X)) is executed, the [S YNCH -C] Open transition representing the request for process- probability of the tuple retrieved to be colour(blue) or space synchronisation upon template T , which leads colour(red)) is exactly 40% or 60%, respectively. to the snapshot: uinT .P | ht1 , .., tn i ,→ T −→ uinT .P | hta, ta, tb, tci ↑ {(ta, 21 ), (tb, 14 ), (tc, 14 )} uinT .P | ht1 , .., tn i ↑ {(t1 , v1 ), .., (tn , vn )} ta −→ 12 where vi=1..n = µ(T, ti ), and µ(·, ·) is the standard P [ta/T ] | hta, tb, tci matching function of L INDA, hence ∀i, vi ::= 1 | 0. [C LOSE -C] Closed unlabelled transition (reduction) representing the internal computation assigning probabilities to III. E XPRESSIVENESS synchronisation items (uniform distribution computa- tion): In [11], authors demonstrate that L INDA-based languages cannot implement probabilistic models: a L INDA process cal- uinT .P | ht1 , .., tn i ↑ {(t1 , v1 ), .., (tn , vn )} culus, although Turing-complete, is not expressive enough to ,→ express probabilistic choice [11]. In our specific case, the gain uinT .P | ht1 , .., tn i ↑ {(t1 , p1 ), .., (tn , pn )} of expressiveness is formally proven in [12], where uniform v primitives are formally proven to be strictly more expressive where pj = Pn j vi is the absolute probability of than standard L INDA coordination primitives by exploiting i=1 retrieving tuple tj , with j = 1..n. probabilistic modular embedding (PME) [10], an extension [E XEC -C] Open transition representing the probabilistic response to modular embedding [13] explicitly meant to capture the to the requested synchronisation (the sampling): expressiveness of stochastic systems. uinT .P | ht1 , .., tn i ↑ {.., (tj , pj ), ..} In particular, if we denote with U L INDA the L INDA co- tj −→pj ordination model where standard getter primitives rd and in P [tj /T ] | ht1 , .., tn i\tj are replaced with uniform getter primitives urd and uin, then U L INDA is proven to be strictly more expressive than L INDA where [·/·] represents term substitution in process P according to PME, since U L INDA probabilistically embeds continuation, and \ is multiset difference, expressing (p ) L INDA, but not the other way around—so that formally, removal of tuple tj from the tuple space. according to PME, L INDA and U L INDA are not observationally equivalent (6≡o ): 2) Semantics of urd (uniform reading): As for standard L INDA getter primitives, the only difference between uniform U L INDA p L INDA, L INDA 6p U L INDA reading (urd) and uniform consumption (uin) is the non- =⇒ U L INDA 6≡o L INDA destructive semantics of the reading primitive urd. This is reflected by E XEC -R open transition: Since formally asserting a gap in expressiveness does not [E XEC -R] The same as E XEC -C, except for the fact that it does not necessarily make it easy for the reader to fully appreciate remove matching tuple how much this can make the difference for adaptive and urdT .P | ht1 , .., tn i ↑ {.., (tj , pj ), ..} self-organising systems, in the remainder of this section we tj discuss two examples showing how uniform primitives make −→pj it possible to (i) have some self-organising property appear by P [tj /T ] | ht1 , .., tn i emergence (Subsection III-A), and (ii) straightforwardly design whereas other transitions are left unchanged. stochastic systems reproducing some simple yet meaningful nature-inspired behavioural pattern, such as pheromone-based 3) Example: As an example, in the following system state coordination (Subsection III-B). uinT .P | hta, ta, tb, tci 1 LogicTuple templ; where µ(T, tx) holds for x = a, b, c, the following synchroni- 2 while(!die){ sation transitions are enabled: 3 templ = LogicTuple.parse("ad(S)"); ta 4 // Pick a server probabilistically (a) uinT .P | hta, ta, tb, tci −→0.5 P [ta/T ] | hta, tb, tci 5 op = acc.urd(tid, templ, null); tb 6 // Plain Linda version (b) uinT .P | hta, ta, tb, tci −→0.25 P [tb/T ] | hta, ta, tci 7 // op = acc.rd(tid, templ, null); tc 8 if (op.isResultSuccess()) { (c) uinT .P | hta, ta, tb, tci −→0.25 P [tc/T ] | hta, ta, tbi 9 service = op.getLogicTupleResult(); 10 // Submit request For instance, if transition (a) wins the probabilistic selection, 11 req = LogicTuple.parse( then the system evolves according to the following trace— 12 "req("+service.getArg(0)+","+reqID+")" simplified by summing up cardinalities and probabilities in 13 ); order to enhance readability: 14 acc.out(tid, req, null); 15 } uin .P | hta, ta, tb, tci 16 } T T −→ uinT .P | hta, ta, tb, tci ↑ {(ta, 2), (tb, 1), (tc, 1)} Fig. 1. Java code for clients looking for services. Fig. 2. Clients using rd primitive: service provider 1 is under-exploited. Fig. 3. Clients using urd primitive: a certain degree of fairness is guaranteed, based on self-organisation. A. Load Balancing for our simulation – the TuCSoN coordination middleware In order to better explain what the “basic mechanisms [14], [15] –: since provider 1 is almost unused, we understand enabling self-organising coordination” actually are – that is, that rd is implemented as a FIFO queue, always matching the a minimal construct able (alone) to impact the observable first tuple among many ones—provider 2 advertising tuple, properties of a coordinated system – we discuss the following in this case. The point here is that such a prediction was not scenario: two service providers are both offering the same ser- possible prior to the simulation, and with no information about vice to clients – through proper “advertising tuples” –; the first the actual L INDA implementation used. is slower than the second, that is, it needs more time to process a request—thus modelling differences in computational power. By using primitive urd instead (Fig. 3), we know – and can predict – how much each service provider will be exploited Their working cycle is quite simple: a worker thread gets by clients: since we know by design that after successfully requests from a shared tuple space, then puts them in the serving a request a provider emits an advertising tuple, and that master thread (the actual service provider) bounded queue. The such tuples are those looked for by clients, we know that the master thread continuously polls the queue looking for requests faster provider will produce more tuples, hence it will be more to serve: when one is found, it is served, then the master frequently found than the slower one. From Fig. 3 charts, in emits another advertising tuple; if none is found, the master fact, we can see how the system of competing service providers does something else, then re-polls the queue—no advertising is self-organises by splitting incoming requests. Furthermore, done. The decoupling enforced by the queue is useful to model such split is not statically designed or superimposed, but the fact that service providers should not block on the space results by emergence from a number of run-time factors, such waiting for incoming requests, so as to be free of performing as clients interactions, service providers computational load, other jobs meanwhile—e.g. reporting, resource clean-up, etc. computational power, and memory. It should also be noted The queue is bounded to model memory constraints. that such form of load balancing is not the only benefit In this setting, clients (whose Java code is listed in Fig. 1) gained when using urd over rd: actually, the urd simulation search for available services first via rd primitive (Fig. 2), successfully serves ' 1600 requests – distributed among then via urd (Fig. 3). All charts’ values are not single runs, providers 1 and 2 according to uniform primitive semantics – but average values resulting from different runs—e.g., value losing ' 600, whereas the rd simulation serves successfully plotted at time step 60 is not that of a single run, but the ' 1250 – leaving provider 1 unused – losing over 2500. average of the number of requests observable at time step 60 of a number of runs (actually, 30). B. Pheromone-based coordination By using the rd primitive we blindly commit to the actual In pheromone-based coordination used by ants to find implementation of the L INDA model currently at hand. For in- optimal paths – as well as by many ant-inspired computational stance, Fig. 2 gives some hints about the implementation used systems, such as [16], [17] – each agent basically wanders Fig. 4. Digital ants search food (top box) wandering randomly from their Fig. 5. By urd-ing digital pheromones left while carrying food, digital ants anthill (bottom box). stochastically find the optimal path toward the food source. randomly through the network until it finds a pheromone trail, neighbour tuple occurs more than once in the local tuple which the agent is likely to follow based on the trail “strength”. space: so, by using uniform primitives, the tuple corresponding Here, aspects such as pheromone release, scent, and evap- to a neighbour place with a pheromone trail has a greater oration [16] are not relevant: instead, the above-mentioned probability to be chosen than the others. notions of “randomness” and “likelihood” are on the one hand For instance, say p1, p2, p3 are neighbour places. Without essential for pheromone-based coordination, on the other hand a pheromone trail, an ant in p1 moves to either p2 or p3 with require uniform primitives to be designed using a tuple-based the same probability, starting from the following system state: coordination model. In particular, we consider a network of n nodes representing places pi , with i = 1..n, through which urd(n(X)).P | hn(p2), n(p3)i ant agents walk. The default tuple space in node pi contains at least one neighbour tuple n(pj ) for each neighbour node pj and the neighbourhood relation is reflexive—so, if node pi There, the enabled synchronisation transitions are and pj are neighbours, pi tuple space contains tuple n(pj ) (a) urd(n(X)).P | hn(p2), n(p3)i and pj tuple space contains tuple n(pi ). Pheromone deposit n(p2) in node pi is modelled by the insertion of a new tuple n(pi ) −→ 0.5 in every neighbour node pi . P [p2/X] | hn(p2), n(p3)i Thus, ants wandering through places and ants following (b) urd(n(X)).P | hn(p2), n(p3)i trails can both be easily modelled using uniform primitives: ant n(p3) agents just need to look locally for neighbour tuples through a −→ 0.5 urd(n(P)). If no pheromone trail is to be detected nearby, P [p3/X] | hn(p2), n(p3)i every neighbour place is represented by a single tuple, so all neighbour places have the same probability to be chosen— that is, an ant agent in p1 has the same probability (50%) to thus leading to random wandering of ants. In case some of move to either p2 or p3—which exactly models random ant the neighbours contains a detectable trail, the corresponding wandering. Instead, if a pheromone trail involves p3 – so that for Our experiments are conducted in a toy scenario involving instance p1 contains 2 tuples n(p3) – the initial system state digital ants and pheromones programmed in ReSpecT [18] would be upon the TuCSoN coordination middleware [14]. The experi- ment involves ten digital ants starting from the anthill with the urd(n(X)).P | hn(p2), n(p3), n(p3)i goal of finding food, and follows the “canonical” assumptions of ant systems. So, at the beginning, any path has equal There, the enabled synchronisation transitions are probability of being chosen, thus modelling random walking of ants in absence of pheromone. As ants begin to wander around, (c) urd(n(X)).P | hn(p2), n(p3), n(p3)i eventually they find food, and release pheromone on their path n(p2) while coming back home. As a consequence, the shortest path −→ 0.3 eventually gets more pheromone since it takes less time to P [p2/X] | hn(p2), n(p3), n(p3)i travel on it rather than on the longest path. Pheromones as well as connections between tuple centres are modelled as described (d) urd(n(X)).P | hn(p2), n(p3), n(p3)i n(p3) above, with “neighbour” tuples: the more neighbour tuples of −→ 0.6 a certain type, the more likely ants will move to that neighbour P [p3/X] | hn(p2), n(p3), n(p3)i tuple centre with their next step. Fig. 4 and Fig. 5 depict a few screenshots of our toy which exactly models the fact that the ant agent in p1 is scenario: there, five distributed tuple centres (the larger boxes) more likely to move to p3 than to p2, thus (probabilistically) model a topology connecting the anthill (bottom box) to a following the pheromone trail. food source (top box): the leftmost path is longer, whereas A crucial point, here, is to understand the issue of system the rightmost is shorter. The green “spray-like” effect on paths predictability with / without uniform primitives. Reachable (black lines) models the strength of the pheromone scent: the states for the system above would not change by replacing greater and greener the path, the more pheromones lay on it. urd with rd: the transitions above would work in the same By plotting pheromones strength evolution over time, Fig. 6 way apart from probabilistic labelling. This essentially means simply shows how our expectations about digital ants be- that a standard L INDA coordinated system would potentially haviour are met: in fact, despite starting from the situation in reach the same states as the one with uniform primitives: the which any path is equi-probable (the amount of pheromones on point is, nevertheless, that quantitative information would be the shortest path is the same as on the longest path), eventually available for the latter system, not for the former. the system detects the shortest path, which becomes the most In particular, in the second example above, the reachable exploited—and contains in fact more pheromone units. states are (c) P [p2/X] | hn(p2), n(p3), n(p3)i and (d) In the Java code describing the behaviour of ants (Fig. 7), in P [p3/X] | hn(p2), n(p3), n(p3)i. Using urd, we know particular in method smellPheromone() (line 10), usage that states (c) and (d) would be reached with probability .3 and of the uniform primitive urd is visible on line 27, whereas .6, respectively: so, both a probabilistic prediction on the single line 29 shows the tuple template given as its argument, that system run, and a statistic prediction over multiple system runs is, n(NBR): at runtime, NBR unifies with a TuCSoN tuple are made possible by the use of uniform primitives. The usage centre identifier, making it possible for the ant to move there. of rd, instead, allows for nothing similar: we just know that Quite obviously, the idea here is not just showing a new both states (c) and (d) could be reached, but no quantitative way to model ant-like systems. Instead, the example above predictions of any sort are possible. is meant to point out how a non-trivial behaviour – that is, dynamically solving a shortest path problem – can be achieved by simply substituting uniform primitives to traditional L INDA getter primitives—which instead would not allow the system to work as required. Furthermore, the solution is adaptive, fully distributed, and based upon local information solely – thus, it appears by emergence –, and robust against topology changes—a ReSpecT specification implementing evaporation was used, although not shown for the lack of space. IV. R ELATED W ORKS Uniform primitives were first used in [19] as a tool for solving a specific coordination problem, called collective sort: however, neither there, nor in subsequent papers [20], [8], they were given but a few lines of informal definition, and their general role in the coordination of complex computational systems was not yet clarified. In [21], similar primitives are presented and formally Fig. 6. Pheromones strength across time. Descending phase corresponds to defined to forge the biochemical tuple space notion, leading a food depletion in food tuple centre: no new pheromones added, evaporation makes strength decline. tuple space to act as a chemical simulator. There, tuples are enriched with an activity/pertinency value – similarly to the quantitative information defined in [11] – to resemble chemical which we call interaction-driven – where probabilistic be- concentrations, therefore L INDA primitives are necessarily haviour is (i) associated to communication primitives – thus, refined with the ability to consider such numerical label. So, neither to processes (or schedulers), nor to tuples – and (ii) the main point of difference w.r.t. therein defined primitives is enacted during the interaction between a process and the that (i) here we rely on tuples multiplicity to model probability, coordination medium—that is, solely through such primitives. leaving the L INDA tuples structure untouched, (ii) uniform primitives are scheduled and executed as L INDA classical get- Also, uniform primitives can be seen as complementary ter primitives, while in [21] their primitives have a stochastic to both the approaches taken in ProbLinCa and P K LAIM, rate of execution equipped. where the basic L INDA model is changed quite deeply. Uni- form primitives, instead, extend L INDA by specialising stan- To the best of our knowledge, proposals presented to extend dard L INDA primitives, without changing neither tuple struc- L INDA with probabilities follow two main approaches [22]: ture nor scheduling policy. Furthermore, uniform primitives could be used to emulate both approaches: tuple weights could • data-driven models, where the quantitative informa- be reified by their multiplicity in the space, whereas probabilis- tion required to model probability is associated with tic scheduling could be obtained by properly synchronising the data items – the tuples – in the form of weights. processes upon probabilistic consumption of shared tuples. This approach is adopted in ProbLinCa [11], the Moreover, uniform coordination primitives could be used in probabilistic version of a L INDA-based process calcu- place of L INDA standard ones without affecting the model, lus. merely refining don’t care non-determinism as probabilistic • schedule-driven models, where the quantitative in- non-determinism: as a result, all the expressiveness results and formation is added to the processes using special all the applications based on the canonical L INDA model do “probabilistic schedulers”. This is the approach taken still hold using uin and urd instead of in and rd. by [22] to define a probabilistic extension of the More complex coordination models exist in literature for K LAIM model named P K LAIM. which uniform primitives could play a key role in providing the probabilistic mechanisms required for the engineering of Instead, our approach belongs to a third, novel category – stochastic systems like adaptive and self-organising ones. S TO K LAIM [23] is an extension to K LAIM in which 1 while (!stopped) { process actions are equipped with rates affecting execution 2 if (!carryingFood) { probability, and execution delays as well—that is, time needed 3 // If not carrying food to carry out an action. By reifying action rates as tuples in 4 isFood = smellFood(); 5 if (isFood) { the space, with multiplicity proportional to rates, uniform- 6 // pick up food if any reading such tuples would allow to probabilistically schedule 7 pickFood(); actions’ execution à la S TO K LAIM. Furthermore, delays could 8 } else { be emulated, too, by uniform-reading a set of “time tuples”, 9 // or stochastically follow pheromone where a higher value corresponds to a lower action rate. 10 direction = smellPheromone(); 11 move(direction); SAPERE [5] is a biochemically-inspired model for the 12 } engineering of complex self-organising and adaptive pervasive 13 } else { service ecosystems, where agents share LSAs (Live Semantic 14 // If carrying food Annotation), which could be thought of as a special kind of 15 if (isAnthill()) { tuples, representing them in shared contexts, and allowing them 16 // drop food if in anthill to interact and pursue their own goals. LSAs are managed 17 dropFood(); through eco-laws, which are some sort of chemical-like rules, 18 } else { scheduled according to their rates Hence, uniform primitives 19 // or move toward anthill could play in SAPERE the same role as in S TO K LAIM—once 20 direction = smellAnthill(); 21 move(direction); eco-laws are reified as tuples with a multiplicity proportional to 22 } execution rate. Furthermore, from the pool of all LSAs which 23 } can participate in a eco-law, the ones actually consumed by the 24 } law – as chemical reactants – are selected probabilistically. 25 Once again, such behaviour could be enabled by uniform 26 private LogicTuple smellPheromone() { consumption of reactant LSAs in eco-laws. 27 ITucsonOperation op = acc.urd( 28 tcid, V. C ONCLUSION 29 LogicTuple.parse("n(NBR)"), 30 TIMEOUT In this paper we formally define uniform primitives as 31 ); simple specialisation of standard L INDA coordination prim- 32 if (op.isResultSuccess()) { itives, exploiting probabilistic non-determinism in place of 33 return op.getLogicTupleResult(); don’t know non-determinism. We argue that uniform primitives 34 } 35 } introduce a simple yet powerful mechanism enhancing tuple- based coordination with the ability to express and predict stochastic behaviours, thus to design complex coordinated Fig. 7. Java code for ants. systems featuring adaptiveness and self-organisation. ACKNOWLEDGMENTS [14] A. Omicini and F. Zambonelli, “Coordination for Internet application development,” Autonomous Agents and Multi-Agent This work has been supported by the EU-FP7-FET Proac- Systems, vol. 2, no. 3, pp. 251–269, Sep. 1999, special Issue: tive project SAPERE – Self-aware Pervasive Service Ecosys- Coordination Mechanisms for Web Agents. [Online]. Available: tems, under contract no. 256874. http://dx.doi.org/10.1023/A:1010060322135 [15] TuCSoN, “Home page,” 2013. [Online]. Available: R EFERENCES http://tucson.unibo.it [16] M. Dorigo and T. Stützle, Ant Colony Optimization. [1] D. Gelernter and N. Carriero, “Coordination languages and their Cambridge, MA: MIT Press, Jul. 2004. [Online]. Available: significance,” Communications of the ACM, vol. 35, no. 2, pp. 97–107, http://mitpress.mit.edu/books/ant-colony-optimization 1992. [Online]. Available: http://dx.doi.org/10.1145/129630.129635 [17] H. V. D. Parunak, S. Brueckner, and J. Sauter, “Digital pheromone [2] P. Wegner, “Why interaction is more powerful than algorithms,” mechanisms for coordination of unmanned vehicles,” in 1st Communications of the ACM, vol. 40, no. 5, pp. 80–91, May 1997. International Joint Conference on Autonomous Agents and Multiagent [Online]. Available: http://dx.doi.org/10.1145/253769.253801 systems, C. Castelfranchi and W. L. Johnson, Eds., vol. 1. New York, [3] D. Gelernter, “Generative communication in Linda,” ACM Transactions NY, USA: ACM, 15–19 Jul. 2002, pp. 449–450. [Online]. Available: on Programming Languages and Systems, vol. 7, no. 1, pp. 80–112, http://dx.doi.org/10.1145/544741.544843 Jan. 1985. [Online]. Available: http://dx.doi.org/10.1145/2363.2433 [18] A. Omicini and E. Denti, “From tuple spaces to tuple centres,” Science [4] A. Omicini and M. Viroli, “Coordination models and languages: of Computer Programming, vol. 41, no. 3, pp. 277–294, Nov. 2001. From parallel computing to self-organisation,” The Knowledge [Online]. Available: http://dx.doi.org/10.1016/S0167-6423(01)00011-9 Engineering Review, vol. 26, no. 1, pp. 53–59, Mar. 2011, [19] M. Casadei, L. Gardelli, and M. Viroli, “Simulating emergent properties special Issue 01 (25th Anniversary Issue). [Online]. Available: of coordination in Maude: the collective sort case,” in 5th International http://dx.doi.org/10.1017/S026988891000041X Workshop on the Foundations of Coordination Languages and Software [5] F. Zambonelli, G. Castelli, L. Ferrari, M. Mamei, A. Rosi, Architectures (FOCLASA 2006), ser. Electronic Notes in Theoretical G. Di Marzo, M. Risoldi, A.-E. Tchao, S. Dobson, G. Stevenson, Computer Science, C. Canal and M. Viroli, Eds. CONCUR 2006, Y. Ye, E. Nardini, A. Omicini, S. Montagna, M. Viroli, Bonn, Germany: Elsevier Science B.V., 31 Aug. 2006, pp. 59—80. A. Ferscha, S. Maschek, and B. Wally, “Self-aware pervasive [Online]. Available: http://dx.doi.org/10.1016/j.entcs.2007.05.022 service ecosystems,” Procedia Computer Science, vol. 7, pp. 197–199, [20] M. Casadei, M. Viroli, and L. Gardelli, “On the collective Dec. 2011, proceedings of the 2nd European Future Technologies sort problem for distributed tuple spaces,” Science of Computer Conference and Exhibition 2011 (FET 11). [Online]. Available: Programming, vol. 74, no. 9, pp. 702–722, 2009, Special Issue http://dx.doi.org/10.1016/j.procs.2011.09.006 on the 5th International Workshop on Foundations of Coordination [6] S. Mariani and A. Omicini, “Molecules of Knowledge: Self- Languages and Architectures (FOCLASA ’06). [Online]. Available: organisation in knowledge-intensive environments,” in Intelligent http://dx.doi.org/10.1016/j.scico.2008.09.018 Distributed Computing VI, ser. Studies in Computational Intelligence, [21] M. Viroli and M. Casadei, “Biochemical tuple spaces for self-organising G. Fortino, C. Bădică, M. Malgeri, and R. Unland, Eds., vol. 446. coordination,” in Coordination Languages and Models, ser. LNCS, Springer, 2013, pp. 17–22, 6th International Symposium on Intelligent J. Field and V. T. Vasconcelos, Eds. Lisbon, Portugal: Springer, Distributed Computing (IDC 2012), Calabria, Italy, 24-26 Sep. 2012. Jun. 2009, vol. 5521, pp. 143–162, 11th International Conference Proceedings. [Online]. Available: http://dx.doi.org/10.1007/978-3-642- (COORDINATION 2009), Lisbon, Portugal, Jun. 2009. Proceedings. 32524-3 4 [Online]. Available: http://dx.doi.org/10.1007/978-3-642-02053-7 8 [7] A. Omicini, “Nature-inspired coordination models: Current [22] A. Di Pierro, C. Hankin, and H. Wiklicky, “Probabilistic Linda-based status, future trends,” ISRN Software Engineering, vol. 2013, coordination languages,” in 3rd International Conference on Formal 2013, article ID 384903, Review Article. [Online]. Available: Methods for Components and Objects (FMCO’04), ser. LNCS, F. S. http://dx.doi.org/10.1155/2013/384903 de Boer, M. M. Bonsangue, S. Graf, and W.-P. de Roever, Eds. [8] L. Gardelli, M. Viroli, M. Casadei, and A. Omicini, “Designing Berlin, Heidelberg: Springer, 2005, vol. 3657, pp. 120–140. [Online]. self-organising MAS environments: The collective sort case,” in Available: http://dx.doi.org/10.1007/11561163 6 Environments for MultiAgent Systems III, ser. LNAI, D. Weyns, [23] R. De Nicola, D. Latella, J.-P. Katoen, and M. Massink, “StoKlaim: H. V. D. Parunak, and F. Michel, Eds. Springer, May 2007, vol. 4389, A stochastic extension of Klaim,” Istituto di Scienza e Tecnologie pp. 254–271, 3rd International Workshop (E4MAS 2006), Hakodate, dell’Informazione “Alessandro Faedo” (ISTI), Tech. Rep. 2006-TR-01, Japan, 8 May 2006. Selected Revised and Invited Papers. [Online]. 2006. [Online]. Available: http://www1.isti.cnr.it/˜Latella/StoKlaim.pdf Available: http://dx.doi.org/10.1007/978-3-540-71103-2 15 [9] M. Bravetti, “Expressing priorities and external probabilities in process algebra via mixed open/closed systems,” Electronic Notes in Theoretical Computer Science, vol. 194, no. 2, pp. 31–57, 16 Jan. 2008. [Online]. Available: http://dx.doi.org/10.1016/j.entcs.2007.11.003 [10] S. Mariani and A. Omicini, “Probabilistic modular embedding for stochastic coordinated systems,” in Coordination Models and Languages, ser. LNCS, C. Julien and R. De Nicola, Eds. Springer, 2013, vol. 7890, pp. 151–165, 15th International Conference (COORDINATION 2013), Florence, Italy, 3–6 Jun. 2013. Proceedings. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-38493-6 11 [11] M. Bravetti, R. Gorrieri, R. Lucchi, and G. Zavattaro, “Quantitative information in the tuple space coordination model,” Theoretical Computer Science, vol. 346, no. 1, pp. 28–57, 23 Nov. 2005. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2005.08.004 [12] S. Mariani and A. Omicini, “Probabilistic embedding: Experiments with tuple-based probabilistic languages,” in 28th ACM Symposium on Applied Computing (SAC 2013), Coimbra, Portugal, 18– 22 Mar. 2013, pp. 1380–1382, Poster Paper. [Online]. Available: http://dx.doi.org/10.1145/2480362.2480621 [13] F. S. de Boer and C. Palamidessi, “Embedding as a tool for language comparison,” Information and Computation, vol. 108, no. 1, pp. 128–157, 1994. [Online]. Available: http://dx.doi.org/10.1006/inco.1994.1004