Behavior Predictability Despite Non-Determinism in the SAPERE Ecosystem Preliminary Ideas Gabriella Castelli, Marco Mamei, Alberto Rosi, Franco Zambonelli Dipartimento di Scienze e Metodi dell’Ingegneria University of Modena and Reggio Emilia, Italy Email: {name.surname}@unimore.it Abstract—How can we have confidence that self organizing this way the non determinism of the self-aware layer systems actually do what we expect them to? In this position is shielded from the actual system functionalities. paper we overview some mechanisms at the basis of controlling 2) Confidence from large numbers. Systems function- and predicting the behavior of autonomous and self-organizing systems despite components’ autonomy and non-deterministic alities are realized on the basis of the average behavior behavior. In particular we focus the analysis on the SAPERE of a large set of components. While the behavior ecosystem as an exemplary model to frame the discussion. We of individual components can be erratic the overall identify three main directions with which to gain confidence average behavior is stable. on the overall system behavior: (i) confidence from layering, 3) Confidence from the structure and dynamics of the (ii) confidence from large numbers, (iii) confidence form the structure and dynamics of the state space. In the paper we state space. Analyzing the state space of the overall describe this ideas and their implication in the design of self system, it is possible to identify more general mech- organizing applications. anisms that guarantees the fulfillment of requested functionalities. I. I NTRODUCTION To ground the discussion we focus the analysis on the The increasing evolution and spread of pervasive comput- SAPERE model and middleware [17], as an exemplary self- ing technologies is defining the basis for the emergence of a organizing ICT system. dense and global decentralized infrastructure for the creation Despite this focus, we think that the proposed ideas are of general-purpose pervasive services. more general and could be fruitfully applied to a wider range In particular, such novel pervasive application scenarios of models and systems. call for adopting self-organizing service coordination ap- In the remaining of this paper we first present the proaches comprising autonomous and adaptive components SAPERE model in order to ground the discussion on a to interact and coordinate with each other to provide services concrete setting. Then, in Section 3-5 we present the dif- and applications. ferent approaches to obtain confidence in the behavior of A number of approaches, taking inspiration from swarm the systems. Finally, Section 6 concludes discussing some intelligent examples [9], [12], [8], try to achieve the above research directions to exploit these ideas. results by making use of a large number of simple au- tonomous components, that self-organize to achieve a de- II. T HE SAPERE M ODEL AND M IDDLEWARE sired application. Examples in this direction are the work SAPERE takes its primary inspiration from natural on collective robotics [12], [13], autonomous and adaptive ecosystems, and starts from the consideration that the dy- systems and distributed computing [17], [18], [6]. namics and decentralization of future pervasive networks One of the main scientific questions in this kind of will make it suitable to model the overall world of services, scenarios is: data, and devices as a sort of distributed and spatially- How can we have confidence that self organizing systems situated computational ecosystem. However, unlike the many actually do what we expect them to? proposals that adopt the term ecosystem simply as a mean Providing convincing answers to that questions is funda- to characterize the complexity and dynamics of ICT systems mental to engineer robust and dependable systems based on [15], SAPERE brings the adoption of natural metaphors the above self-organizing principles. down to the core of its approach, by exploiting nature- In this position paper we present thee main directions inspired mechanisms (and in particular bio-chemical ones showing guidelines on to design self organizing applications [16]) for actually ruling the overall system dynamics. so as to retain confidence in their behavior. In particular we Specifically (see Figure 1), SAPERE models a pervasive identified three main mechanisms to be considered service environment as a non-layered spatial substrate, laid 1) Confidence from layering. System’s reliable func- above the actual pervasive network infrastructure. The sub- tionalities are realized on top of the self-aware layer. In strate embeds the basic laws of nature (or eco-laws) that rule the activities of the system. It represents the ground on which individuals of different species (i.e., the components of the pervasive service ecosystem) interact and combine with each other (in respect of the eco-laws and typically based on their spatial relationships), so as to serve their own individual needs as well as the sustainability of the overall ecology. Users can access the ecology in a decentralized way to use and consume data and services, and they can also act as “prosumers” by injecting new data or service components. For the components living in the ecosystem, SAPERE adopts a common modeling and treatment of services, data, and devices. All “entities” living in the ecosystem will have an associated semantic representation (in the case of pure data items, the entity and its representation will Figure 1. The SAPERE Conceptual Architecture coincide), which is a basic ingredient for enabling dynamic unsupervised interactions between components. To account for the high dynamics of the scenario and for its need of continuous adaptation, SAPERE will define such annotations as living, active entities, tightly associated to the component they describe, and capable of reflecting its current situation and context. Such Live Semantic Annotations (LSAs) will thus act as observable interfaces of resources and services, as well as the basis for enforcing semantic and self-aware forms of dynamic interactions (both for service aggrega- tion/composition and for data/knowledge management). For the eco-laws driving the dynamics of the ecosystem, SAPERE envisions them to define the basic policies to drive virtual chemical reactions among the LSAs of the various individuals of the ecology [2], [16]. In particular, Figure 2. The SAPERE Middleware on a Node of the Network. the idea is to enforce, on a spatial basis and possibly relying on diffusive spatial mechanisms [10], dynamic networking and composition of data and services. In particular, data ure 2). In particular, it reifies LSAs in the form of tuples, and services (as represented by their associated LSAs) will dynamically stored and updated in a system of highly- be sorts of chemical reagents, and interactions and com- distributed tuple spaces spread over the nodes of the network positions will occur via chemical reactions, i.e., semantic [10]. pattern-matching, between LSAs. Such reactions will con- The active components of the ecosystem (whether ser- tribute establishing virtual chemical bonds between entities vices, software agents, sensing/actuating devices, or data (e.g., relating similar services with each other to produce a sources) express their existence via LSAs injected in the lo- distributed service, or mining related data items) as well cal tuple space associated to their node. Then, they indirectly as producing new components (e.g. a composite service interact with each other via such tuple space by observing orchestrating the execution of atomic service components or and accessing their own LSA. a high-level knowledge concept derived from the aggregation In SAPERE an agent can see only its own LSA and of raw data items). the LSAs that are bonded to. There are not general read Adaptivity in SAPERE will not be in the capability of operations. An agent can inject an LSA. This LSA will form individual components, but rather in the overall dynamics bonds with other LSAs (bond are created by means of eco- of the ecosystem. In particular, adaptivity will be ensured laws – see below). Only after that, that agent can read those by the fact that any change in the system (as well as any other LSAs. change in its components, as reflected by dynamic changes The eco-laws represent sorts of virtual chemical reactions in their LSAs) will reflect in the firing of new chemical between LSAs, and get activated by processes embedded in reactions, thus possibly leading to the establishment of new tuple spaces (which make SAPERE tuple spaces different bonds and/or in the breaking of some existing bonds between from traditional tuple spaces). Such processes evaluate the components. potentials for establishing new chemical bonds between From an implementation viewpoint, SAPERE relies on LSAs, the need for breaking some, or the need for lightweight and minimal middleware infrastructure (see Fig- generating new LSAs from the combination of existing 2 crowd steering [11]. In this kind of task, gradients indicating direction to be followed are spread in the environment. 1 3 Agents navigate the space by simply following the gradient uphill or downhill depending on the application. 2 Gradients distributed configuration can be maintained by a set of decentralized autonomous agents that propagate it in the environment. The typical process at the basis of this mechanisms is extremely non-deterministic. As the agents 2 are not centrally coordinated nor synchronized the gradient can be propagated and maintained with different timings 1 3 among different and un predictable network routes (see Fig. 3). 2 4 Is this kind of un-predictability an issue in our crowd steering applications? It is not. Despite the unpredictability in how the gradient propagates, the final result is that eventually the gradient is properly laid out (see Fig. 3). In this example a reliable and Figure 3. The gradient assumes a final coherent distribution, disregarding its unpredictable propagation. dependable service: the steering gradient, is built on top on an unreliable and unpredictable substrate. Another similar example is represented by gossip-based ones. In addition, to support distributed spatial interactions, aggregation in sensor network [4]. In this kind of systems eco-laws can enforce the diffusion of LSAs to spatially global aggregated values are computed in a decentralized close tuple spaces, e.g., to those tuple spaces that are way via the local exchange of messages among distributed neighbor to each other in the network, according to specific nodes. For example, if nodes have to compute the average propagation patterns (gradient-based diffusion, broadcast, value of some sensed property over an area, they can follow or multicast). this simple algorithm: 1) Each node sets its estimated average to its current In this kind of systems, the dynamics in the tuple space sensor readings. tend to be rather complex, as all the interaction patterns are 2) Each node selects a neighbor node. The two nodes reified in pattern matching operations among LSAs and eco- exchange their current estimates. laws. 3) Each node updates its estimate as the average of its Accordingly, the central question of this paper: how can current estimate and the neighbor’s one. we have confidence that self organizing systems actually do 4) Nodes cyclically repeat step 2 and 3 what we expect them to? is very relevant for this kind of It is rather easy to show that this algorithm allows each systems. estimate to rapidly converge to the actual average value [4]. In the next sections we present thee main directions Also in this case, despite interactions among devices can showing guidelines on to design self organizing applications follow unpredictable dynamics, the final result is stable. so as to retain confidence in their behavior: (i) confidence Accordingly, application built on top of that computed from layering, (ii) confidence from large numbers, (iii) average do not suffer from unpredictability in that the confidence form state space analysis. computed average “layer” shields the application from low- level unpredictability. III. C ONFIDENCE FROM LAYERING Several other examples of this same behavior can be System’s reliable functionalities are realized on top of the found in [14]. In all of them, different kind of data self-aware layer. In this way the actual system functionalities decouples application functional requirements form the are shielded from the non determinism of the self-aware unpredictable agent dynamics that produces the data itself. layer. This kind of approach toward control is typical in spatial Insights for SAPERE and amorphous computing [1], [10]. A number of applica- tions in this area are built on the basis of interaction patterns In SAPERE we developed a number of mechanisms to arising from the creation and diffusion of gradients (a.k.a. support such kind of “stable” data structures. In particular, fields) in the environment. a set of eco-laws in SAPERE act as aggregation operators. Gradients are distributed data structures propagated in a These eco-laws basically implement order and duplicate spatial computer and conveying spatial information about insensitive aggregation functions such as (min, max, average, components. A typical example of the use of gradients is in etc.) [4]. These eco-laws can be used to properly propagate and maintain a gradient LSA so that is is properly spread Insights for SAPERE across the network [18]. Similarly, they can be used to aggregate distributed LSAs so as to provide a compact In SAPERE we developed algorithms relying on such a description of environmental properties (in term of a suitable large-number effect [14]. These algorithms allow to trans- LSA). form and organize LSAs’ populations in a coherent and As discussed above, despite the dynamics of the SAPERE reliable way despite underlying non deterministic pattern eco-system is highly non-deterministic, applications built on matching. top such LSAs would be stable and predictable. V. C ONFIDENCE FROM THE STRUCTURE AND DYNAMICS IV. C ONFIDENCE FROM LARGE NUMBERS OF THE STATE SPACE Another complementary approach to get confidence over Thinking of the system’s behavior in terms of its state the behavior of the system is based on adopting a large space, it is possible to identify methods and mechanisms to number of components to average out unpredictability in understand how the system will evolve over time. the behavior of components. In particular, if we are able to identify some properties of System’s functionalities are realized on the basis of the the system than are maintained by all the possible system average behavior of a large set of components. While the dynamic, then we can confidently build applications on such behavior of individual components can be erratic, the overall properties. average behavior is stable. To ground the discussion, let’s focus on the latter example Algorithms and mechanisms proposed in the vision of in the previous section: we have indeterminism every time an swarm intelligence often rely on this kind of approach. eco-law can be applied to multiple LSAs. More in general, For example, ant based sorting [9] is an example of this in Linda-like systems, unpredictability arises when multiple technique. One self-organized behavior enabling this kind pattern matches can fire concurrently. In this case, the system of sorting is that individual agents just wander randomly will evolve differently depending on which pattern matching and pick up and drop items according to the number of is triggered first. similar surrounding objects. For example, if an individual Thinking of the state space of the system, there are two agent finds a large cluster of similar items together with cases in which such an indeterminism does not lead to a different one, it will most likely pick up the misplaced unpredictability: (i) the state space is modeled so that – item and start roaming around. That individual will probably from the application functional requirements’ viewpoint – deposit its load in a region containing other items similar all the possible evolution of the system are the same. (ii) The to the one he is carrying. While the low level behavior of underlying mechanisms ensure that all the possible states of individual agents is largely erratic and non deterministic, it is the system are actually visited. possible to show that system evolves to a globally coherent In simple terms: either the system visits only states that state in which items are clustered. are indistinguishable from each other form the application Another example, very relevant in the context of the viewpoint, or the systems visits all the possible states. In SAPERE vision, is related to artificial chemistry [18]. This both the cases, unpredictability vanishes. In the following example matches very closely the working of the SAPERE of this section, we consider the two cases separately. ecosystem: a large number of LSAs (metaphorically chem- ical components) are subject to a number of Eco-laws A. Indistinguishable States (metaphorically chemical reactions). If the unpredictability in the system evolution involves If the same eco-law can be applied to multiple LSAs, we states that are indistinguishable from the application per- have indeterminism, and thus unpredictability in the way in spective, there are not problems in controlling the system. which the system will evolve. In the SAPERE framework, a typical example of this One way to avoid this kind of situations is by relying case is considering service-oriented scenarios. In this case, – as in chemistry – on large (theoretically Avogadro-like) multiple services (e.g., S1 and S2) can expose via the LSA numbers of LSA. In this way, all the possible products a given functionality X. Another service can express in of Eco-laws are produced and unpredictability vanishes as its LSA the fact it wants to bind with X. Indeterminism application designers are guaranteed that all the possible in the way which eco-laws are applied does not allow the reactions will take place and all the possible products will programmer to predict whether the service will bind with appear. S1 or S2. However this is not a problem, since from the In both the above examples it is possible to see that, if application viewpoint S1 and S2 are indistinguishable as an application is built on top of such collectively-produced they provide the same functionality X. functionalities, then application’s evolution is predictable As another example, the mechanisms that lead to the despite the mechanisms underlying non determinism. diffusion of a gradient in the system can be interpreted as op- erations than move the system in the state space to a “point” corresponding to the state in which the gradient is properly If(bind with LSA1): laid out. Because of the underlying non-determinism the function1() system may take different trajectories to reach than point, If(bind with LSA2): but eventually the proper state will be reached. Disregarding function2() transient behaviors, the trajectories followed by the system If(there are both LSA1 and LSA2): are indistinguishable by a “gradient-following” application function3() – like crowd steering – that only relies on the resulting gradient. From this viewpoint, the case of indistinguishable states actually generalizes the – confidence from layering – described in the previous section. Insights for SAPERE LSA Randomly selected bond Following this kind of ideas, when creating an application in the SAPERE framework, it is important to design LSAs so LSA1 LSA2 that pattern matching can only happen among LSAs that are equivalent (indistinguishable) from the application perspec- tive. In general, to achieve this property in open scenarios, it is important rely on common ontologies or namespaces in Figure 5. Since SAPERE agent cannot perform generic read operation on the SAPERE space, the agent executes non deterministically function1 order to actually ensure the complete indistinguishability in or function2. It can never execute function3. On the contrary, if the agent the states of the system that can be possibly reached. could see that both LSA1 and LSA2 are present in the SAPERE space, then it will deterministically chose function3 B. All States Another condition under which unpredictability vanishes is in the case the system generates all the possible states. this happens, we have unpredictability in that the system To clarify this concept, let us focus on a SAPERE randomly visit a state excluding the others (see Fig. 4.a). application in which an agent’s LSA can bind with both To solve this issue and regain predictability the way in LSA1 and LSA2. However, the two bindings are not indis- which the pattern matching process applies to eco-laws has tinguishable (like the in the previous Section) and the agent to be changed. The intuition is that if the creation of a bond will behave differently depending on which LSAs will be between two LSAs does not prevent other bonds from being bound. Looking at Fig. 5, the agent will execute function1 created, the ergodicity is restored and the system is again or function2 non deterministically. predictable. Accordingly there are two possibilities: The problem is that since pattern matching is non deter- 1) For each eco-law there must exist the opposite eco- ministic the agent will be bound with LSA1 or LSA2 and law that disrupts the bond being created. In this way, it does not even know that the other LSA (LSA2 or LSA1) the disruption of a bond allows other kind of bonds was existing. Looking at Fig. 5, the agent will be never able to be realized. Thus it enables the exploration of the to execute function3. Recall from Section 2 that SAPERE whole state space (see Fig. 4.b). agent cannot read the SAPERE space, they can just perceive 2) The bonding mechanisms does not prevent other bonds LSAs with which they are bound. from happening and thus an LSA can always be bond On the contrary, if the agent could see that both LSA1 and with multiple other LSAs at the same time. Also in LSA2 are present in the SAPERE space, then the system this case, all the reactions that could happen, actually evolution would be predictable and specified by the agent happen and again the whole state space is visited (see code: looking at Fig. 5, the agent will deterministically chose Fig. 4.c). function3. It is possible to notice that this ergodic viewpoint gen- This situation is the realm of ergodic processes and eralizes the – confidence from large numbers – described systems [19]. In signal processing, a stochastic process is in the previous section. In that case, ergodicity is simply said to be ergodic if its statistical properties can be deduced guaranteed by the law of large numbers applied to the from a single, sufficiently long sample (realization) of the uniform random process that fires eco-laws to different process. This implies that an ergodic process visits all the LSAs. Also in this case all the reactions that could happen, state space. actually happen because since the number of LSA is large In general, pattern matching operations like in SAPERE the probability that one eco-law is excluded form pattern are not ergodic as the creation of a bond between two matching – because of the random schedule – goes to zero. LSAs can prevent other bonds from being created. When There is actually another definition of ergodicity that property_x = A property_x = A property_x = A A) property_x = ? Random Choice property_x = ? property_x = ? property_x = B of which bind to property_x = B The system property_x = B trggger never gets here property_x = A property_x = A property_x = A property_x = A Bond New bond is property_x = ? B) property_x = ? Random Choice of property_x = ? disrupted property_x = ? given a property_x = B chance property_x = B property_x = B which bind to property_x = B trggger property_x = A property_x = A property_x = A Random property_x = ? Also other property_x = ? C) property_x = ? Choice of property_x = B bond can be property_x = B which bind to created property_x = B trggger Figure 4. A) Non ergodicity in pattern matching, B) Ergodicity via bond disruption, C) ergodicity via multiple bonds states that: a system in which the phase-space averages statistics on the expected behavior of the systems once the correspond to the time averages is called an ergodic.. The above control mechanisms are enforced. – confidence from large numbers – rely on phase-space In addition we will try to get better theoretical insights average, while the previous two dynamics possibilities in the system’s dynamic of SAPERE applications. In related to time averages. particular, we will try to apply techniques such as Petri nets [3] and model checking [7] to formally understand and Insights for SAPERE describe the possible dynamics of the system. Ergodicity allows a SAPERE agent to see the whole range Acknowledgements: Work supported by the SAPERE (Self- of LSAs to be possibly bound. The agent will then decide Aware Pervasive Service Ecosystems) project (EU FP7-FET, how to behave on the basis of such an information. In this Contract No. 256873). case, despite non determinism in the order in which pattern R EFERENCES matching is fired, the agent is able to act deterministically by fully analyzing its context (i.e., the kind of bonds that [1] J. Bachrach, J. Beal, and T. Fujiwara. Continuous space-time semantics allow adaptive program execution. In IEEE In- can be established). ternational Conference on Self-Adaptive and Self-Organizing Systems, Boston (CA), USA, 2007. VI. C ONCLUSIONS AND R ESEARCH D IRECTIONS In this position paper we tried to address one of the main [2] J.-P. Banâtre and T. Priol. Chemical programming of future challenges in the development of self-organizing applica- service-oriented architectures. Journal of Software, 4(7):738– 746, 2009. tions comprising autonomous agents, namely: How can we have confidence that systems which are self-aware and adapt [3] F. Bause and J. Kriege. Detecting non-ergodic simulation according to their beliefs actually do what we expect them models of logistics networks. In International conference to?. on Performance evaluation methodologies and tools, Nantes, France, 2007. We present three main research avenues on which to ground confidence on the system-level behavior of the [4] N. Bicocchi, M. Mamei, and F. Zambonelli. Self-organizing system: (i) confidence via layering, (ii) confidence via large virtual macro sensors. ACM Transaction on Autonomous numbers, (iii) confidence from the structure and dynamics Adaptive Systems, 7(1), 2012. of the state space (that subsumes also the other two cases). [5] R. Bird, W. Stewart, and E. Lightfoot. Transport Phenomena. Al these mechanisms well apply to the SAPERE model Wiley, 1976. and can have an impact on similar approaches in different areas. [6] G. Cabri, M. Puviani, and F. Zambonelli. Towards a taxonomy of adaptive agent-based collaboration patterns for autonomic In our future work we will detail and experiment the service ensembles. In International Conference on Collab- presented ideas. In particular we will run experiments using oration Technologies and Systems, Philadelphia (PA), USA, the SAPERE middleware and simulation tools to gather 2011. [7] E. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 1999. [8] S. Dobson, S. Denazis, A. Fernandez, D. Gaiti, E. Ge- lenbe, F. Massacci, P. Nixon, F. Saffre, N. Schmidt, and F. Zambonelli. A survey of autonomic communications. ACM Transactions on Autonomous and Adaptive Systems, 1(2):223–259, 2006. [9] M. Mamei, R. Menezes, R. Tolksdorf, and F. Zambonelli. Case studies for self-organization in computer science. Jour- nal of Systems Architecture, 52:443–460, 2006. [10] M. Mamei and F. Zambonelli. Programming pervasive and mobile computing applications: the tota approach. ACM Trans. Software Engineering and Methodology, 18(4), 2009. [11] M. Mamei, F. Zambonelli, and L. Leonardi. Co-fields: A physically inspired approach to distributed motion coordina- tion. IEEE Pervasive Computing, 3(2):52–61, 2004. [12] G. Pini, A. Brutschy, M. Frison, A. Roli, M. Dorigo, and M. Birattari. Task partitioning in swarms of robots: An adaptive method for strategy selection. Swarm Intelligence, 5(3). [13] T. Schmickl, R. Thenius, C. Mslinger, J. Timmis, A. Tyrrell, M. Read, J. Hilder, J. Halloy, A. Campo, C. Stefanini, L. Manfredi, T. Dipper, D. Sutantyo, and S. Kernbach. Cocoro the self-aware underwater swarm. In Awarenss Workshop, Ann Arbor (MI), USA, 2011. [14] A. Tchao, M. Risoldi, and G. Serugendo. Modeling self-* systems using chemically-inspired composable patterns. In IEEE International Conference on Self-Adaptive and Self- Organizing Systems, Ann Arbor (MI), USA, 2011. [15] M. Ulieru and S. Grobbelaar. Engineering industrial ecosys- tems in a networked world. In 5th IEEE International Conference on Industrial Informatics, pages 1–7, June 2007. [16] M. Viroli, M. Casadei, S. Montagna, and F. Zambonelli. Spatial coordination of pervasive services through chemical- inspired tuple spaces. ACM Transactions on Autonomous and Adaptive Systems, 6(2):14, 2011. [17] M. Viroli, E. Nardini, G. Castelli, M. Mamei, and F. Zam- bonelli. A coordination approach to adaptive pervasive service ecosystems. In Awarenss Workshop, Ann Arbor (MI), USA, 2011. [18] M. Viroli, D. Pianini, S. Montagna, and G. Stevenson. Per- vasive ecosystems: a coordination model based on semantic chemistry. In ACM Symposium on Applied Computing (SAC 2012), Riva del Garda, Italy, 2012. ACM. [19] P. Walters. An introduction to ergodic theory. Springer, 1982.