Coordinating Spatially-Situated Pervasive Service Ecosystems Mirko Viroli, Elena Nardini Gabriella Castelli, Marco Mamei, Franco Zambonelli A LMA M ATER S TUDIORUM – Università di Bologna Università di Modena e Reggio Emilia Cesena, Italy Reggio Emilia, Italy {mirko.viroli, elena.nardini}@unibo.it {gabriella.castelli, marco.mamei, franco.zambonelli}@unimore.it Abstract—Technology evolution is providing new pervasive interacting with each other without being forced to face service scenarios characterised by a huge number of dis- significant re-engineering to incorporate innovations and tributed and dynamic devices. Accordingly, a new generation changes. To meet these above requirements, one should no of services and infrastructures are emerging which support situatedness, adaptivity and diversity. In this paper we model longer conceive services and their coordinated activities as the overall world of services, data and devices, as a distributed in ad hoc solutions or on the basis of standard service- computational ecosystem. Each entity will be modelled as oriented architectures [8]. There, services are simply func- an autonomous, spatially-situated individual of the ecosystem, tional entities coordinated according to mostly static (hardly whose existence is reified by an LSA (Live Semantic Anno- self-adaptable) patterns. tation). Ecosystem’s behaviour is controlled by coordination rules called eco-laws, which are sort of chemical-like reactions Recent proposals in the area of coordination models and evolving the population of LSAs. We describe an architecture middleware for pervasive computing scenarios try to account supporting this vision, a formal model of eco-laws, and finally for issues related to spatiality [12], [13], spontaneous and show their usefulness in a scenario of crowd steering through opportunistic coordination [1], [7], self-adaptation and self- pervasive displays. management [19]. But, in most of the cases, the proposals face these issues via one-of solutions to specific problems I. I NTRODUCTION in specific areas, and lacking generality and comprehen- The increasing evolution and spread of pervasive com- siveness. Tackling the problem in a more radical way, we puting technologies is defining the basis for the emer- argue that a promising direction is that of re-thinking current gence of a dense and global decentralised infrastructure for service architectures and coordination approaches by taking the creation of general-purpose pervasive services. These inspiration from natural systems, where spatial concepts include traditional classes of services enriched with the and features of self-adaptation, self-management, and long- capability of dynamically and autonomously adapting to lasting evolvability are inherently there because of the basic the context in which they are exploited (a public display “rules of the game”. showing advertisements based on the preferences of the Nature-inspired solutions have already been extensively majority of people around), as well as innovative services exploited in the area of distributed computing for the imple- for better perceiving/interacting with the physical world (a mentation of specific middleware solutions or of specific dis- PDA hosting a real-time map showing where are my friends tributed services [11], and similarly, natural and ecological around and what are they doing). Such a scenario will metaphors have been adopted to characterise the complexity feature a number of diverse sensing devices, personal and of modern ICT and service systems [20]. Here we pursue public displays, personal mobile devices, and humans, all a line of research that intends to go further than adopting of which to be dynamically engaged in very dynamic and natural system as an inspiration for specific solutions as a flexible coordinated activities. In particular, the specific co- generic metaphor: we aim at exploiting a natural metaphor ordination requirements for such novel pervasive application to shape a reference architecture around which to conceive, scenarios include: (i) the capability to naturally match the model, and develop a fully-fledged coordination framework spatial nature of the environment and of the services within, for pervasive service systems. which involves managing coordinating activities between Although natural systems can be categorised in different components that are physically co-located or close to each classes (e.g., physical [12], chemical [22], biological [2], other; (ii) the capability to inherently facilitate spontaneous or social [10]), they all account for a spatial environmen- interactions among components, without requiring an a tal substrate, and autonomous individuals (i.e., agents) of priori knowledge of each other, and making the resulting different kinds getting in touch, interacting, competing, and patterns of interactions self-adaptive and self-managing; (iii) combining with each other – in one word, coordinating – the capability to flexibly tolerate evolutions of structure and in respect of some basic “laws of nature”. Accordingly, we diversity over time, which is necessary to account for a claim that a truly self-adaptive shared pervasive substrate large (and evolving) number of very diverse components will have to be conceived as the space in which bringing to will have an associated semantic representation called Live Semantic Annotations (LSAs, yellow blocks). To account for high dynamics of the scenario and for its need of continu- ous holistic adaptation, we will consider such annotations as living, active entities, capable of reflecting the current situation and context of the component they describe. They will act as actual observable interfaces of resources (devices, users, software services), as well as the basis for enforcing semantic and self-aware forms of dynamic interactions (both for service aggregation/composition and for data/knowledge management). The eco-laws drive the dynamics of the ecosystem. We envision them to define the basic policies to rule sorts of virtual chemical reactions among the LSAs of the various Figure 1. The SAPERE logic architecture individuals. In particular, the idea is to enforce dynamic concept-based (i.e., semantic and goal-oriented) networking, life an ecosystem of service agents coordinated by some composition, and coordination of data and services. We will basic laws (which we call “eco-laws”) of the ecosystem consider data and services (as represented by their associated that will provide self-organisation, self-management, and LSAs) as sorts of chemical reagents in an ecology in evolvability. Along these lines, the key contributions of this which interactions and composition occur via chemical-like article are as follows: reactions, i.e., semantic pattern-matching between LSAs. • we frame the key concepts of the nature-inspired ar- Such reactions can contribute to establish virtual chemical chitecture at the basis of our coordination approach bonds between entities (e.g., relating similar services with and of the SAPERE project (“Self-aware Pervasive each other to produce a distributed service, or mining related Service Ecosystems”, www.sapere-project.eu), in which data items) as well as to produce new components (e.g. a our research activities situate (Section 2); composite service coordinating the execution of atomic ser- • we detail the model of “eco-laws” that underlies the vice components or a high-level knowledge concept derived overall dynamics of the ecosystem, and that act as from the aggregation of raw data items). spatial coordination laws over a shared distributed Coordination and adaptivity in the SAPERE framework space (resembling a tuple space scenario), promoting are not bound inside the capability of individual components, spontaneous and opportunistic interactions among the but rather emerge in the overall dynamics of the ecosystem. components of the ecosystem (Section 3); In particular, they are ensured by the fact that any change • we present case studies related to coordinated context- in the system (as well as any change in its components, as awareness and visualisation in an environment pervaded reflected by dynamic changes in its LSA) will reflect in the by interactive displays, which are of particular rele- firing of some eco-law possibly leading to the establishment vance for crowd steering applications (Section 4). of new bonds and/or in the breaking of some existing bonds. Related works in coordination models and languages (Sec- That is, the SAPERE architecture promotes adaptivity and tion 5) and a discussion on final remarks and future works coordination not by creating self-awareness at the level of (Section 6) conclude the paper. components, but rather promoting a sort of “systemic self- awareness”. II. T HE SAPERE C OORDINATION A RCHITECTURE Such way of enforcing adaptation can also tolerate long- The coordination approach of the proposed SAPERE term system evolution. In fact, even if we do not assume (and model takes its primary inspiration from natural ecosys- do not deal with) the capability of individual components to tems, adopting a chemical inspired mechanism to rule the evolve, it is the injection of new updated components in spatially-coordinated activities of the components (devices, the system – automatically incorporated in the ecosystem services, and humans) and, thus, the overall system dynamics coordination dynamics – that provide for a sort of seamless [16]. From the architectural viewpoint, we consider struc- evolution. That is, as in natural selection, it is species turing a pervasive service environment (see Figure 1) as of components that evolve, not individuals: more suitable a non-layered spatial substrate, mapped above the actual component classes replace out-of-date ones in the ecosystem pervasive network infrastructure, which is composed by a dynamics, without requiring any specific adjustment to the possibly very dense set of hardware devices. infrastructure or to the other components. The spatial substrate embeds the basic laws of nature (or From an implementation-oriented viewpoint, the SAPERE eco-laws) that rule the activities of the system. The com- framework will be realised as a lightweight and minimal ponents (green blocks), living in the envisioned substrate, middleware that will reify LSAs in the form of tuples, to be dynamically stored and updated in a system of spatially- is a sum of LSA “patterns” P . One such pattern can be situated tuple spaces spread over the devices of the network. void (0), can specify the identifier of an LSA (ι), its tag Eco-laws will take place in the network nodes in order to (type), or that property p either holds term t (hp=ti) or promote seamless adaptivity and coordination. This archi- should be added/removed with a value (+= and -=). A term tecture will also boost the participation of users that access t is a value, possibly including some unconstrained variable the ecology in a decentralised way to use and consume data {x}, or an annotated variable {x : x f t} that should and services, and they can also act as prosumers by injecting (semantically) match t by function f —such functions f , new data or service components (possibly also for the sake which are typically application-dependent, are binary fuzzy of controlling the ecology behaviour). predicates over values, yielding a real number in between 0 (no match) and 1 (full match). Finally, the whole ecosystem III. T HE E CO - LAWS FRAMEWORK E is a multiset composition of eco-laws L, LSA-spaces hSiσ To define in a more precise way ecosystems behaviour, (σ is the space identifier), and space connections σ σ0 . and shade light to the SAPERE coordination model, in this For the sake of space we do not formally model well- section we introduce a core calculus of eco-laws, capturing formedness of eco-laws, which dictate the possibility of the key aspects and mechanisms of the proposed framework, using remote identifiers – as well as operators “+=” and which include: (i) syntactic structure of LSAs and eco-laws, “-=” – only in the right hand side; additionally, each (ii) application of eco-laws to LSAs (and related fuzzy pattern can specify at most one occurrence of an LSA matching mechanisms), (iii) bond establishment, and (iv) identifier, a type, and a property. diffusion mechanisms to achieve spatial-aware behaviour. Although not properly a process algebra, we adopt a Auxiliary functions We introduce a congruence relation related formalisation approach for our calculus, as e.g. “≡”, to equip the above syntax with additional features. We developed in [21], [4], [14]—see Section 5 for a comparison. first establish equivalence of the following notations, which will be useful to match an LSA with a pattern: Syntax We model the state of an ecosystem as a networked set of LSA-spaces, each carrying a set of LSAs; each LSA is a tuple of property/value associations, and an eco-law is ι : typehp1 =v1 , . . . , pn =vn i ≡ ι, type, hp1 =v1 i, . . . , hpn =vn i as a reaction (in a multiset rewrite style) over patterns of LSAs residing in the same LSA-space—with the possibility We introduce equations giving semantics to an update func- of moving LSAs to a neighbouring space, resembling so- tion R J A, which takes the right-hand side R of an eco-law called “firing tuples” introduced in [21]. and an LSA A to which the eco-law has to be applied, and Let meta-variable σ range over LSA-space identifiers, d enacts all updates specified in R which pertains A: over primitive data values (literals, and numerals r including ∞ – used for an arbitrary large number), x over logic (P + R) J A ≡ (P J A) + (R J A) 0JA≡0 variables, p over property names, type over LSA tags, f (ι, P ) J (ι, P 0 ) ≡ ι, (P 0 / P ) (ι, P ) J (ι0 , P 0 ) ≡ (ι, P ) if ι 6= ι0 over semantic match functions, and λ over LSA unique P / (P 0 , P 00 ) ≡ (P / P 0 ) / P 00 0/P ≡P identifiers. The (static and runtime) syntax of the model is P, hp=vi / p=v 0 ≡ P, hp=v 0 i P, type 0 / type ≡ P, type expressed by the following grammar: P, hp=vi / hp+=v i ≡ P, hp=v · v 0 i 0 P, hp=v · v 0 i / hp-=v 0 i ≡ P, hp=vi P, hp=vi / hp0 o v 0 i ≡ (P / hp0 o v 0 i), hp=vi if p 6= p0 ι ::= λ|λ id of local/remote LSA A ::= ι : typehp1 =v1 , . . . , pn =vn i LSA v ::= λ | d | v1 · . . . · vn value Namely, operator “J” affects the left-hand side only if it S ::= 0 | A | (S | S) LSA-space L ::= R 7→r R0 eco-law specifies the same LSA as the right-hand side, in which case R ::= 0|P |R+R reagent set it proceeds by updating through operator /, which in turn P ::= 0 | ι | type | hp op ti | (P, P ) pattern changes (replaces, adds or removes) values of all properties op ::= = | += | -= update/access operator t ::= v | t1 · . . . · tn | {x} | {x : x f t} term of the LSA. For instance (for the case of a single-reagent E ::= 0 | L | hSiσ | σ σ 0 | (E | E) ecosystem R), we have: An LSA A includes the unique identifier ι, type tag, and a (λ, type, hc=5i, ha+=3i) J λ : typeha=5, b=4i ≡ λ : typeha=5 · 3, b=4, c=5i set of property/value associations p1 =v1 , . . . , pn =vn (pi are not repeated). A value v can be an identifier λ (modelling a bond towards its LSA), primitive data value d or a sequence Finally, we consider “≡” as the largest relation which, other v1 · . . . · vn . An LSA-space S is a composition of LSAs by than equations above, also handles operators “+”, “ | ”, “,”, operator “ | ”. and “·” as multiset ones (i.e, commutative, associative, and An eco-law L is a chemical-resembling reaction trans- absorbing 0). forming a reagent set R into R0 by speed r; a reagent set Matching Given any syntactic structure s (an eco-law L, an LSA A, and so on), we use standard nota- tion [v1 /x1 , . . . vn /xn ]s for s after substituting variables x1 , . . . , xn with values v1 , . . . , vn —this is syntactic as usual, i.e., [v/x]{x} = [v/x]{x : x f v 0 } = v. We now need Local context aware coordination Eco-laws a mechanism to match the partial specification of a pattern LSAs P with the complete one of an LSA A: we hence abuse the notation writing [A/P ] for the most general substitution (if any exists) which applied to pattern (A, P ) equates it to A (note this makes sense only if properties in A and P do not clash); for instance: Spatial Coordinated Visualization Eco-laws LSAs [λ : typehn=lit, s=40, u=λ1 ·λ2 i/({i}, type, hu = λ1 ·{u}i, hs={s}i)] Eco-laws LSAs yields substitution [λ/i, 40/s, λ2 /u]. Figure 3. (top). Local Context-Aware Coordination A public dis- play collects and merges together detailed information about several user Finally, following and refining the approach in [21], profiles. bottom). Spatial Coordinated Visualisations Public displays we introduce a mechanism of fuzzy/semantic matching, by interact to present coherent coordinated content (e.g., to provide steering which we rate the extent to which an LSA matches a patter. and directions) to users. Function µ(A, P ) ∈ [0, 1] is introduced to this end—note this will be actually used only if notation [A/P ] actually yields a substitution, which simplifies definition below. This reached: it takes one pattern P in the left-side of the eco- function is defined as follows: law, and tries to match it with some LSA A in space σ. The resulting state S 0 in space σ is computed by recursively µ((id, type, P ), (id0 , type0 , P 0 )) = µ(P, P 0 ) applying (Re) to a space without A, without P in the eco- µ((hp=vi, P ), (hp={x : x f v 0 }i, P 0 )) = µ(P, P 0 ) ∗ f (v, v 0 ) law, by applying substitution [A/P ] to the remainder of the µ(P, P 0 ) = 1 otherwise eco-law, and finally updating the right-hand side with LSA So, considering the application-dependent function A. Finally, rule (Df) is used to ship (at an arbitrary high matches, we have e.g.: rate) some remote LSA with id λ, tag type, and properties µ( λ : typehn=basket, s=40i, P , from space σ into a neighbouring space σ 0 . λ : typehn={x : x matches sport}, s=40i ) = matches(basket, sport) IV. U SE CASES Operational semantics The operational semantics of this Displays providing information are one of the first tech- calculus is given as a CTMC (Continuous-time Markov nologies that is truly becoming pervasive and ubiquitous. Chains) model, like other stochastic calculi for chemical-like Public displays are gradually deployed everywhere: from behaviour [21]. A transition system (E, →, R+ 0 ) is defined airports and stations to city centres. At the same time, r where transitions are of the kind E − → E 0 , meaning that an increasing number of people carry on private displays ecosystem in state E ∈ E moves to E 0 ∈ E, by either an embedded in their smart phones. These devices are grad- eco-law reaction or by an LSA diffusion, with Markovian ually provided with sensing and networking capabilities rate r ∈ R+0 —namely the transition duration is a stochastic to perceive their environment and act accordingly. Since variable following negative exponential distribution with displays can (and should) interact with each other the average value 1/r time units. resulting scenario is that of an ecosystem of displays more The transition relation is defined by the rules in Figure 2. deeply fulfilling users’ information needs. Given the massive Rule (C) and (P) provide standard semantics of congruence amount of devices comprising such an ecosystem, a natural and parallel composition: the former states that transitions coordination problem arises: how can displays coordinate are to be applied modulo congruence “≡”; the latter that their activities to optimise the user experience? How can any subsequent rule is actually local, since any ecosystem displays acquire data from sensors and elaborate them so subpart E 0 is allowed to move to a E 00 in isolation. Rule (Ef) as to get an overall better representation of the context? handles the special case of an eco-law with no reagents, in How can displays coordinate so as to steer a crowd in a which case simply the right-hand side R of the eco-law is spatial system? We here discuss some case study involving formed by LSAs to be inserted in any space σ with rate r. different coordination patterns to be enacted by the display Rule (Re) is recursive, and uses (Ef) when termination is ecosystem in the form of suitable eco-laws. r E ≡ E1 E1 −−−→ E10 E10 ≡ E 0 (C) r E −−−→ E 0 r E 0 −−−→ E 00 (P) r E | E −−−→ E | E 00 0 − (Ef) r (0 7→r R) | hSiσ −−−→ (0 7→r R) | hS | Riσ r0 (R[A/P ] 7→r R0 [A/P ] J A) | hSiσ −−−−→ L | hS 0 iσ (Re) 0 r ∗µ(A,P ) (P + R 7→r R0 ) | hA | Siσ −−−−−−−→ (P + R 7→r R0 ) | hS 0 iσ − (Df) ∞ h(λ , type, P ) | Siσ | σ σ 0 | hS 0 iσ0 −−−−→ hSiσ | σ σ 0 | h(λ, type, P ) | S 0 iσ0 Figure 2. Operational Semantics of Eco-laws A. Local Context-Aware Coordination visualisation service: in particular, a service is added only if the required screen properties p’ match with the available The eco-law framework can support public displays in screen properties p—matches function is here in charge retrieving data from different kinds of sensor and to use them of (possibly semantically) match display property lists, fa- to infer high-level context information, either automatically cilitating connection with compatible services. or through some external recommendation system. Let’s consider the case of a public area (a mall, an airport) A decision about which service is to be visualised at a where some people wander around with their portable device given time is made by updating property showFrom in (e.g. a smartphone) that keep their profile. Additionally, such the display’s LSA. The display can achieve this in two user devices embed a number of sensors that may be used ways. On the one hand, it monitors its LSA, reasons about for inferring what the user is doing (e.g., the microphone can context property (it can access LSAs of sensors, users, be used for inferring if the user is talking with someone, the and service content by navigating LSA references through accelerometer if the user is standing or walking, and so on). its LSA), takes a choice about what service to visualise, A number of public displays are deployed to show different and accordingly reifies it in showFrom property. On the kinds of visualisation services to users, e.g. monitoring, ad- other hand, the display can externalise the decision by vertisements, directions (i.e. crowd steering). Public displays setting recommend property to ask. By eco-law [SEL- have to acquire data about the users standing in front of them ASK] a recommendation LSA is then created with all and get a synthetic representation of what is happening in the necessary information to take a meaningful decision. One order to provide the best possible content to users. Also possibility for getting a reply is by eco-law [SEL-MATCH], public displays have an associated LSA that specifies the which finds a bonded service s whose content matches the display characteristics and enables interactions with users’ display’s context, and accordingly update answer property in proximity. A key role is played by the SAPERE nodes in the recommendation—the semantics of eco-laws make hosting LSA-spaces: they are spread in the environment, and sure that the most proper choice is probabilistically taken. as soon as they sense a device or service around they reify Alternatively, and mostly transparently, as the recommenda- their presence by a proper LSA. In particular, spaces will tion LSA has been created an available recommender agent hosts LSAs for the public displays, the profile and sensors of (which can possibly encapsulate some situation recognition users around, and the visualisation services available in that algorithm) – a pervasive service eventually injected in the context (see Figure 3-top). Eco-laws handling this scenario system to improve the quality of visualisation – can intercept (filling the context of each public display, and accordingly such LSA and provide itself a reply. choosing the most proper visualisation service as a summary As a decision is taken, eco-law [ACT] starts dis- of the current audience), are shown in Figure 4—we use a play/service interaction, by creating a communication chan- concrete syntax that almost fully adhere to the abstract one nel between the display’s LSA (property channel) and a described in previous section. new LSA of type channelProxy, acting as a reification of Eco-law [CTX-SNS] states that a display’s LSA d with the interaction session—channels have not been modelled in property contextualising set to true gets automat- previous section for the sake of space, and for this is a quite ically bonded to any sensor’s LSA s in the same space, orthogonal mechanism. Additionally, by eco-law [LOG] one namely, s gets added to the display’s context property— or more log LSAs are created to store the historical data this happens if s is not already there, in which case this related to the present event, namely, the display d visualising reaction is not fired for it has no neat effect. Similarly, the selected service s to the user u. The above eco-laws eco-laws [CTX-USR] and [CTX-SER] bond the display’s should come with proper rates, to be tuned according to the LSA to that of any user around and of any available needs of the application at hand. {d}:display[contextualizing = true] + {s}:sensor -->[CTX-SNS] {d}:[context += {s}] + {s} {d}:display[contextualizing = true] + {u}:user -->[CTX-USR] {d}:[context += {u}] + {u} {d}:display[contextualizing = true, screenprops = {p}] + {s}:service[screenprops = {p’: p’ matches p}] -->[CTX-SER] {d}:[context += {s}] + {s} {d}:display[recommend = ask, context = {ctx}] -->[SEL-ASK] {d}:display[recommend = asked] + {r}:recommenation[device={d},context={ctx}, question=service] {r}:recommenation[device={d},context={ctx}, question=service] + {s}:service[content={c: c matches ctx}] -->[SEL-MATCH] {s} + {r}:[answer={s}] {d}:display[recommend = asked, context = {ctx}] + {r}:recommenation[device={d}, answer={s}] -->[SEL-REP] {d}:[recommend = received, showFrom = {s}] {d}:display[showFrom={s},channel=null] -->[ACT] {d}:[channel=#sink] + {c}:channelProxy[service={s},display={d},channel=#source] {d}:display[showFrom={s},context has {u}] + {u}:user -->[LOG] {d} + {u} + {l}:log[time=#current-time,user={u},service={s},display={d}] Figure 4. Eco-laws for Local Context-Aware Coordination B. Spatial Coordinated Visualisation function greater-than yields 1 if left-hand argument is greater than right-hand one, 0 otherwise, and similarly The idea of crowd-steering is to guide (steer) a group for is-sum-of. Eco-law [MIN] completes the creation of of users in moving through an environment by providing the field, choosing in each LSA-space the field LSA with visual cues by means of public and private displays. In this smaller distance from the field source. Ultimately, the above use case, we focus on public displays coordinating so as to three eco-laws reify an LSA in each space within range direct users to a near display that is actually providing a distance, carrying a numerical value holding the minimum content that best matches the user’s interest (see Figure 3- distance from the source display—which can hence be used bottom). This scenario involves several interactions patterns: to also identify a minimum path towards it [12]. (i) public displays diffuse information about the content they We assume now we are in the situation in which all are actually visualising; (ii) by such diffused information, displays are contextualised by eco-laws [CTX-SNS,CTX- and by users in front of the screen, displays acquire global USR,CTX-SER], and diffused a computational field by context information; (iii) the infrastructure, by interaction [PUMP,DIFF,MIN], by which the infrastructure can steer with the users’ private displays, can provide them with users: this is achieved by eco-laws [STE-ASK,STE- coherent information to steer them to the most appropriate MATCH,STE-REP], which are structurally similar to [SEL- display. Such behaviour can be enacted by the eco-laws in ASK,SEL-MATCH,SEL-REP]. Eco-law [STE-ASK] inter- Figure 5. cepts the situation in which a user u in front of a displays has Eco-law [PUMP] is used to initiate the generation of a a profile p that does not match currently visualised content computational field [12], namely, a distributed structure of s: in this case, a new recommendation LSA is created, LSAs advertising the existence and state of a display into asking for a proper display for u. Either a recommender a whole part of the network. In particular, as a display or eco-law [STE-MATCH] solve this situation; the latter has the diffuse property set to true, a field LSA looks for the computational field f of a display visualising is locally created. Eco-law [DIFF] is used to make any content c that is compatible with u’s profile, and accordingly field LSA spawn a remote one, with distance property updates recommendation LSA by proposing display d—as updated by adding variable #dist—this will be bound usual, the semantics of eco-laws make sure that the most to the distance of the neighbouring node as soon as this proper choice is probabilistically taken. Then, eco-law [STE- LSA is shipped there. Note this eco-law activates only if REP] incorporates this decision by updating the user’s LSA, distance is smaller than the expected range of the field— i.e., updating property suggestion shall make the user’s {d}:display[diffuse=true,range={r},showFrom{s}] + {s}:service[content={c}] -->[PUMP] {d} + {s} + {f}:field[display={d},content={c},range={r},distance=0] {f}:field[display={d},content={c},distance={r’},range={r:r greater-than r’}] -->[DIFF] remote {f’}:field[display={d},content={c},distance={mt’: mt’ is-sum-of mt,#dist},range={r}] {f}:field[display={d},distance={mt}] + {f’}:field[display={d},distance={mt’: mt’ greater-than mt}] -->[MIN] {f} {d}:display[showFrom={s}, context = {ctx}, context has {u}] + {s}:service[content={c: c not-matches p}] + {u}:user[profile={p}] -->[STE-ASK] {d} + {s} + {u} + {r}:recommendation[subject={u}, context={ctx}, question=display] {r}:recommendation[subject={u}, question=display] {u}:user[profile={p}] + {f}:field[source={d},type={display},content={c: c matches p}] -->[STE-MATCH] {f} + {u} + {r}:recommendation[answer={d}] {u}:user + {r}:recommendation[subject={u}, answer={d}] --> [STE-REP] {u}:user[suggestion={d}] Figure 5. Eco-laws for Coordinated Visualisation PDA signal the recommendation of moving to a new area, character to the language used to program the distributed where the suggested display is located. system behaviour; (ii) providing a reactive computational model very useful in autonomic contexts. While Gamma V. R ELATED W ORK and it extensions (such as HOCL) were exploited in Chemical-oriented coordination The issue we face in this different application contexts [3], they originated with the article can be framed as the problem of finding the proper goal of writing concurrent, general-purpose programming coordination model for enabling and ruling interactions languages. Our approach instead aims at specifically of pervasive services. We take as ground the archetypal tackling coordination infrastructures for pervasive systems, L INDA model, which simply provides for a blackboard with which calls for dictating specific mechanisms of fuzzy associative matching for mediating component interactions matching, diffusion, context- and spatial-awareness, and through insertion/retrieval of tuples. Then, we followed the agent-LSA interaction. idea of engineering the coordination space of a distributed system by some policy “inside” tuple spaces, following Situatedness and Context-Awareness Considering the is- the pioneer works of approaches like TuCSoN [15] and sues of situatedness and context-awareness, extensions or M ARS [5]. In particular, our proposal tries to extend these modifications to the traditional SOAs have been recently models to include bio-inspired ecological mechanisms, by proposed to address adaptivity in pervasive environments. fine-grained and well structured chemical-like reactions. In Similarly to our approach, in PLASTIC [1] service de- particular, the coordination approach we propose in this pa- scriptions are coupled with dynamic annotations related to per originates from the chemical tuple space model in [21], the current context and state of a service, to be used for though with some notable differences: (i) here we provide enforcing adaptable forms of service discovery. However, a detail notational framework to flexibly express eco-laws our approach gets rid of traditional discovery services and that work on patterns of LSAs and affect their properties; enforces dynamic and adaptive service interaction via simple (ii) the chemical concentration mechanisms proposed in [21] chemical reactions and a minimal middleware. to exactly mimick chemistry is not mandatory here—though In many proposals for pervasive computing environments it can be achieved by a suitable design of rate expressions; and middleware infrastructures, the idea of “situatedness” (iii) the way we conceive the overall infrastructure, and has been promoted by the adoption of shared virtual relationship between agents and their LSAs goes beyond spaces for services and components interactions. The the mere definition of the tuple-space model. pioneering system Gaia [18] introduces the concept of Chemistry has been a source of inspiration for several active spaces, that is active blackboard spaces acting as the works in (distributed) computing and coordination like in means for service interactions. Later on, a number of Gaia the Gamma language and its extensions [3]. The main extensions where proposed to enforce dynamic semantic features we inherit from this research thread include: pattern-matching for service composition and discovery (i) conferring a high-level, abstract, and nature-inspired [7] or access to contextual information [6]. Other related approaches include: Egospaces [9], LIME [13] and TOTA focus on: (i) relying on standard technologies like RDF [12]. Our model shares the idea of conceiving components for the actual incarnation of LSAs and eco-laws, (ii) the as “living” and interacting in a shared spatial substrate (of use of OWL ontologies for promoting the conception of an tuple spaces) where they can automatically discover and application-independent set of eco-laws, (iii) the adoption of interact with one another. Yet, our aim is broader, namely, to more advanced spatial mechanisms into eco-laws, to support dynamically and systemically enforce situatedness, service higher-level self-organisation structures of LSAs. interaction and data management with a simple language of chemical reactions, and most importantly, enacting an Acknowldgments This work has been supported by the EU- ecological behaviour. FP7-FET Proactive project SAPERE – Self-aware Pervasive Service Ecosystems – under contract no. 256874. Self-organisation Several recent works exploit the lessons R EFERENCES of adaptive self-organising natural and social systems to enforce self-awareness, self-adaptivity and self-management [1] M. Autili, P. Benedetto, and P. Inverardi. Context-aware adap- features in pervasive computing systems. At the level of tive services: The plastic approach. In FASE ’09: Proceed- ings of the 12th International Conference on Fundamental individual component modelling, these proposals take the Approaches to Software Engineering, pages 124–139, Berlin, form of either situated reactive agents or proactive and Heidelberg, 2009. Springer-Verlag. goal-oriented ones [17]. At the level of interaction models, these proposals typically take the form of specific nature- [2] O. Babaoglu, G. Canright, A. Deutsch, G. A. D. Caro, and socially-inspired interaction mechanisms [2], enforced F. Ducatelle, L. M. Gambardella, N. Ganguly, M. Jelasity, R. Montemanni, A. Montresor, and T. Urnes. Design patterns either at the level of component modelling or via specific from biology for distributed computing. ACM Trans. Auton. middleware-level mechanisms. Adapt. Syst., 1(1):26–66, 2006. We believe our framework integrates and improves these works in three main directions: (i) it abstracts from the [3] J.-P. Banâtre and T. Priol. Chemical programming of future specific internal characteristics of components (no matter service-oriented architectures. Journal of Software, 4:738– 746, September 2009. whether they are simple reactive components or complex goal-oriented ones) and rather proposes an approach that [4] N. Busi, R. Gorrieri, and G. Zavattaro. On the expressiveness seamlessly applies to both cases; (ii) it tries to identify an of linda coordination primitives. Inf. Comput., 156(1-2):90– interaction model that is able to represent and subsume the 121, 2000. diverse nature-inspired mechanisms under a unifying self- adaptive abstraction (i.e. the semantics chemical reactions); [5] G. Cabri, L. Leonardi, and F. Zambonelli. MARS: A programmable coordination architecture for mobile agents. (iii) the ecological approach we undertake goes beyond IEEE Internet Computing, 4(4):26–35, 2000. most of the current studies that limit to ensembles of homogeneous components, defining a suitable framework [6] P. D. Costa, G. Guizzardi, J. P. A. Almeida, L. F. Pires, for supporting the vision of novel pervasive and Internet and M. van Sinderen. Situations in conceptual modeling of scenarios as made up of self-adaptive devices and services, context. In Tenth IEEE International Enterprise Distributed Object Computing Conference (EDOC 2006), 16-20 October that autonomously cooperate for the creation of global 2006, Hong Kong, China, Workshops, page 6. IEEE Computer services. Society, 2006. VI. C ONCLUSION AND F UTURE W ORK [7] C.-L. Fok, G.-C. Roman, and C. Lu. Enhanced coordination In this paper we outlined the SAPERE architecture, fo- in sensor networks through flexible service provisioning. In J. Field and V. T. Vasconcelos, editors, Coordination cussing on the chemical-resembling eco-laws framework for Languages and Models, volume 5521 of LNCS, pages 66– the self-adaptive, context-aware coordination of pervasive 85. Springer-Verlag, June 2009. 11th International Confer- computing systems—although we focussed on the ecosystem ence (COORDINATION 2009), Lisbon, Portugal, June 2009. of display scenario, the proposed model and language could Proceedings. be applicable also to other coordination domains, including [8] M. N. Huhns and M. P. Singh. Service-oriented computing: advanced adaptive and real-time traffic control, and social Key concepts and principles. IEEE Internet Computing, and augmented reality services. The road towards the full 9(1):75–81, 2005. realisation of the SAPERE framework is necessarily longer than the scope of this paper, and includes deeper evalu- [9] C. Julien and G.-C. Roman. Egospaces: Facilitating rapid ation of the proposed model, design of an efficient and development of context-aware mobile applications. IEEE lightweight tuple-space infrastructure supporting LSAs and Trans. Software Eng., 32(5):281–298, 2006. eco-laws, and implementation of use cases based on the [10] M. P. Locatelli, M. Loregian, and G. Vizzari. Artificial most recent pervasive computing technologies. Concerning Societies in a Community-Based Approach to Ambient In- the model described in this paper, current and future works telligence. The Computer Journal, 53(8):1152–1168, 2010. [11] M. Mamei, R. Menezes, R. Tolksdorf, and F. Zambonelli. Case studies for self-organization in computer science. Jour- nal of Systems Architecture, 52(8):443–460, 2006. [12] M. Mamei and F. Zambonelli. Programming pervasive and mobile computing applications: The tota approach. ACM Trans. Softw. Eng. Methodol., 18(4):1–56, 2009. [13] A. L. Murphy, G. P. Picco, and G.-C. Roman. Lime: A coordination model and middleware supporting mobility of hosts and agents. ACM Trans. on Software Engineering and Methodology, 15(3):279–328, 2006. [14] R. D. Nicola, D. Latella, and M. Massink. Formal modeling and quantitative analysis of KLAIM-based mobile systems. In SAC ’05: Proceedings of the 2005 ACM symposium on Applied computing, pages 428–435, New York, NY, USA, 2005. ACM Press. [15] A. Omicini and F. Zambonelli. Coordination for Internet application development. Autonomous Agents and Multi- Agent Systems, 2(3):251–269, Sept. 1999. [16] J. pierre Banâtre, P. Fradet, and Y. Radenac. Classical Coordination Mechanisms in the Chemical Model. 2009. [17] A. Ricci, A. Omicini, M. Viroli, L. Gardelli, and E. Oliva. Cognitive stigmergy: Towards a framework based on agents and artifacts. In D. Weyns, H. V. D. Parunak, and F. Michel, editors, Environments for MultiAgent Systems, volume 4389 of LNAI, pages 124–140. Springer, Feb. 2007. 3rd International Workshop (E4MAS 2006), Hakodate, Japan, 8 May 2006. Selected Revised and Invited Papers. [18] M. Román, C. K. Hess, R. Cerqueira, A. Ranganathan, R. H. Campbell, and K. Nahrstedt. Gaia: a middleware platform for active spaces. Mobile Computing and Communications Review, 6(4):65–67, 2002. [19] P. V. Roy, S. Haridi, A. Reinefeld, J.-B. Stefany, R. Yap, and T. Coupaye. Self-management for large-scale distributed systems: an overview of the selfman project. In Formal Methods for Components and Objects, LNCS No. 5382, pages 153–178. Springer Verlag, 2008. [20] M. Ulieru and S. Grobbelaar. Engineering industrial ecosys- tems in a networked world. In 5th IEEE International Conference on Industrial Informatics, pages 1–7. IEEE Press, 2007. [21] M. Viroli and M. Casadei. Biochemical tuple spaces for self-organising coordination. In Coordination Languages and Models, volume 5521 of LNCS, pages 143–162. Springer- Verlag, June 2009. [22] M. Viroli and F. Zambonelli. A biochemical approach to adaptive service ecosystems. Information Sciences, 180(10):1876–1892, 2010.