Collective Sorting Tuple Spaces Matteo Casadei, Luca Gardelli, Mirko Viroli DEIS, Cesena Alma Mater Studiorum – Università di Bologna via Venezia 52, 47023 Cesena (FC), Italy {m.casadei,luca.gardelli,mirko.viroli}@unibo.it Abstract— Coordination of multiagent systems is recently with the goal of moving tuples from one space to the other moving towards the application of techniques coming from until completely “sorting” them, that is, tuples of different the research context of complex systems: adaptivity and self- types reside in different tuple spaces. We show a solution organisation are exploited in order to tackle openness, dynamism and unpredictability of typical multiagent systems applications. to this problem based on a fully-distributed algorithm, where In this paper we focus on a coordination problem called collective each agent moves tuples according to fully-local criteria, and sorting, where autonomous agents are assigned the task of moving where complete sorting appear to emerge from initial chaotic tuples across different tuple spaces according to local criteria, tuple configurations. To provide evidence of correctness and resulting in the emergence of the complete clustering property. appropriateness we rely on simulations. Using a library we developed for the M AUDE term rewriting system, we simulate the behaviour of this system and evaluate Many simulation tools can be exploited to this end, though some solutions to this problem. they all necessarily force the designer to exploit a given specification language, and therefore better apply to certain I. I NTRODUCTION scenarios and not to others—examples are SPIM [6], SWARM Systems that should self-organise to unpredictable changes [7] and REPAST [8]. Instead of relying on one of them, in their environment very often need to feature adaptivity in this paper we seek for a general-purpose approach. We as an emergent property. As this observation was first made evaluate the applicability of the M AUDE specification tool as a in the context of natural systems, it was shortly recognised general-purpose engine for running simulations [9]. It is very as an inspiring metaphor for artificial systems as well [1]. well known that M AUDE allows for modelling syntactic and However, a main problem with emergent properties is that, dynamic aspects of a system in a quite flexible way, supporting by their very definition, they cannot be achieved through a e.g. process algebraic, automata, and net-like specifications— systematic design: their dynamics and outcomes cannot be all of which can be seen as instantiations of M AUDE’s term fully predicted. Nonetheless, providing some design support in rewriting framework. We developed a library for allowing a this context is still possible. The whole system of interest, that system designer to specify in a custom way a system model in is the application to design and the environment it is immersed terms of a stochastic transition system—a labelled transition in, can be modelled as a stochastic system, namely, a system system where actions are associated with a rate (of occurrence) whose dynamics and duration aspects are probabilistic. In this [10]. One such specification is then exploited by the tool to scenario, simulations can be run and used as a fruitful tool to perform simulations of the system behaviour, thus making predict certain aspects of the system behaviour, and to support it possible to observe the emergence of certain (possibly a correct design before actually implementing the application unexpected) properties. at hand [2]. The remainder of this paper is as follows: Section 2 provides This scenario is particularly interesting for agent coordina- some background on coordination techniques featuring adap- tion. Some works like the TOTA middleware [3], SwarmLinda tivity, Section 3 describes the collective sorting problem, while [4], and stochastic KLAIM [5], though starting from different Section 4 presents the M AUDE model of the Collective Sorting perspectives, all develop on the idea of extending standard and its simulation results, and finally Section 5 concludes coordination models with features related to adaptivity and providing perspectives on future works. self-organization. They share the idea that tuples in a tuple space eventually spread to other tuple spaces in a non- II. BACKGROUND deterministic way, depending on certain timing and probability In the effort to improve the design process of software issues. Accordingly, in this paper we start analysing the systems—i.e. to bridge the gap between the design and the potential role that simulation tools can have in this context, actual implementation—it has become very common practice towards the identification of some methodological approach to take into account not only functional and architectural to system design. requirements, but also quantitative aspects like temporal and As a reference example, we consider an application to probabilistic ones. When dealing with complex systems, it is a tuple space scenario of the so-called collective sorting often the case that aleatory in system dynamics may cause problem for swarm intelligence [1]. This application features the emergence of interesting properties, that cannot therefore autonomous agents managing a set of distributed tuple spaces, be abstracted away when designing the system. Coordination 173 models and technologies for multiagent systems are witness- In several scenarios, sorting tuples may increase the overall ing the development of a number of works moving to this system efficiency. For instance, it can make it easier for an direction, most of which are inspired by natural phenomena. agent to find an information of interest based on its previous A first example is the TOTA (Tuples On The Air) mid- experience: the probability of finding an information where dleware [3] for pervasive computing applications, inspired by a previous and related one was found is high. Moreover, the concept of field in physics—like e.g. the gravitational when tuple spaces contain tuples of one kind only, it is or magnetic fields. This middleware supports the concept of possible to apply aggregation techniques to improve their “spatially distributed tuple”: that is, a tuple can be cloned and performance, and it is generally easier to manage and achieve spread to the tuple spaces in the neighborhood, creating a sort load-balancing. of computational field, which grows when initially pumped Increasing system order however comes at a computational and then eventually fades. To this end, when injected in a price. Achieving ordering is a task that should be generally tuple space, each tuple can be equipped by some application- performed online and in background, i.e. while the system dependent rules, defining how a tuple should spread across the is running and without adding a significant overhead to the network, how the content of the tuple should be accordingly main system functionalities. Indeed, it might be interesting to affected, and so on. TOTA is mainly targeted to support look for suboptimum algorithms, which are able to guarantee multiagent systems whose environment is open, dynamic and a certain degree of ordering in time. unpredictable, like e.g. to let mobile agents meet each other Nature is a rich source of simple but robust strategies: in a dynamic network. the behaviour we are looking for has already been explored Another example is the SwarmLinda coordination model in the domain of social insects. Ants perform similar tasks [4], which though similar to TOTA is more inspired by swarm when organizing broods and larvae: this class of coordination intelligence and stigmergy [1], [11], [12]. In SwarmLinda strategies are generally referred to as collective sorting or tuples are moved from one tuple space to the other, and ant- collective clustering [1]. Although the actual behaviour of like algorithms are used to retrieve them. The use of self- ants is still not fully understood, there are several models that techniques in SwarmLinda derives from necessity of dealing are able to mimic the dynamics of the system. Ants wander with openness and with the unpredictability of a tuple space’s randomly and their behaviour is modelled by two probabilities, users, against the need of achieving adaptivity. respectively, the probability to pick up Pp and drop Pd an item Finally, the “swarm robotics” field applies strategies in-  2  2 spired by social insects in order to coordinate the activities k1 f Pp = , Pd = , (1) of a multiplicity of robots systems. Typically, these systems k1 + f k2 + f are built on top of ad-hoc software middlewares [1], and solve where k1 and k2 are constant parameters and f is the problems with distributed-algorithms where, though each robot number of items perceived by an ant in its neighborhood: brings about very simple goals, the whole system can be f may be evaluated with respect to the recently encountered used to solve quite complex problems—see e.g. the collective items. To evaluate the system dynamics, apart from visualising sorting problem in Section III-A. it, it can be useful to provide a measure of the system order. These are all examples witnessing the fact that coordination Such an estimation can be obtained by measuring the spatial in open, dynamic, and unpredictable systems have quantitative entropy, as done e.g. in [11]. Basically, the environment is aspects playing a very important role. This calls for analysis subdivided into nodes and Pi is the fraction of items within and design tools that can support system development at a node, hence the local entropy is Hi = −Pi log Pi . The sum various levels, from formal specification up to simulations. of Hi having Pi > 0 gives an estimation of the order of the entire system, which is supposed to decrease in time, hopefully III. C OLLECTIVE S ORTING reaching zero (complete clustering). A. General Scenario B. An Architecture for Implementing Collective Sorting We consider a case of Swarm-like intelligence known as We conceive a multiagent system as a collection of agents collective sorting [1]. It features a multiagent system where interacting with/via tuple spaces: agents are allowed to read, the environment is structured and populated with items of insert and remove tuples in the tuple spaces. Additionally, and different kinds: the goal of agents is to collect and move items transparently to the agents, an infrastructure provides a sorting across the environment so as to order them according to an service in order to maintain a certain degree of order of tuples arbitrary shared criterion. This problem basically amounts to in tuple spaces. This service is realised by a class of agents clustering: homogeneous items should be grouped together and that will be responsible for the sorting task. Hence, each tuple should be separated from others. Moving to a typical context space is associated with a pool of agents, as shown in Figure of coordination models and languages, we consider the case 1, whose task is to compare the content of the local tuple space of a fixed number of tuple spaces hosting tuples of a known against the content of another tuple space in the environment, set of tuple types. The goal of agents is to move tuples from and possibly move some tuple. Since we want to perform this one tuple space to the other until the tuples are clustered in task online and in background, and with a fully-distributed, different tuple spaces according to their tuple type. swarm-like algorithm, we cannot compute the probabilities in 174 spaces exist (labelled with identifiers 0, 1, 2 and 3), and four tuple kinds are subject to ordering (’a, ’b, ’c, and ’d). A. A M AUDE library for simulation M AUDE is a high-performance reflective language support- ing both equational and rewriting logic specifications, for specifying a wide range of applications [9]. The basic brick of Fig. 1. The basic architecture consists in a set of sorter agents dedicated to a M AUDE program is the module, which is essentially a set of a single tuple space. definitions determining an algebra: the modules can be either of the functional or system kind. Functional modules contain both (syntax-customed) type and operation declarations, along Equation 1 to decide whether to move or not a tuple: the with equations which are actually equational rewriting rules approach would not be scalable since it requires to count all defining abstract data types—this is hence useful to declare the tuples for each tuple space, which might not be practical. algorithmic aspects of computing systems. System modules Hence, we devise a strategy based on tuple sampling, and can instead have rewriting laws as well—i.e. transition rules— suppose that tuple spaces provide for a reading primitive we that are typically used to implement a concurrent rewriting call urd, uniform read. This is a variant of the standard rd semantics, and are then able to deal with aspects related to primitive that takes a tuple template and yields any tuple interaction and system evolution. In the course of finding a matching the template: primitive urd instead chooses the general simulation tool for stochastic systems, we find M AUDE tuple in a probabilistic way among all the tuples that could as a particularly appealing framework, for it allows to directly be returned. For instance, if a tuple space has 10 copies of model a system in terms of transition rules, or to prototype a tuple t(1) and 20 copies of tuple t(2) then the probability that new domain-dependent language to have more expressiveness operation urd (t(X)) returns t(2) is twice as much as t(1)’s. and compact specifications. As standard Linda-like tuple spaces typically do not implement Using M AUDE, we realized a general simulation framework this variant, it can e.g. be supported by some more expressive for stochastic systems: the idea of this tool is to model model like ReSpecT tuple centres [13]. When deciding to a stochastic system by a labelled transition system where r:a move a tuple, an agent working on the tuple space T SS follows transitions are of the kind S −−→ S 0 , meaning that the system this agenda: in state S can move to state S 0 by action a, where r is the 1) it draws a destination tuple space T SD different from (global) rate of action a in state S. The rate of an action in a the source one T SS ; given state can be understood as the number of times action 2) it draws a kind k of tuple; a could occur in a time-unit (if the system would rest in state 3) it (uniformly) reads a tuple T1 from T SS ; S), namely, its occurrence frequency. This idea is inspired by 4) it (uniformly) reads a tuple T2 from T SD ; the activity mechanism of stochastic π-Calculus [10], where 5) if the kind of T2 is k and it differs from the kind of T1 , each channel is given a fixed local rate, and the global rate of then it moves a tuple of the kind k from T SS to T SD . an interaction is computed as the channel rate multiplied by The point of last task is that if those conditions hold, then the the number of processes willing to send a message and the number of tuples k in T SD is more likely higher than in T SS , number of processes willing to receive a message. Our model therefore a tuple could/should be moved. It is important that is hence a generalisation of this approach, for the way the all choices are performed according to a uniform probability global rate is computed is custom, and ultimately depends on distribution: while in the steps 1 and 2 it guarantees fairness, the application at hand—e.g. the global rate can be fixed, or in steps 3 and 4 it guarantees that the obtained ordering is can depend on the number of system sub-processes willing to appropriate. execute an action. Given a transition system of this kind and an It is worth noting that the success of this distributed al- initial state, a simulation is simply executed by: (i) checking gorithm is an emergent property, affected by both probability each time the available actions and their rate; (ii) picking and timing aspects. Will complete ordering be reached starting one of them probabilistically (the higher the rate, the more from a completely chaotic situation? Will complete ordering likely the action should occur); (iii) accordingly changing be reached starting from the case where all tuples occur in the system state; and finally (iv) advancing the time counter just one tuple space? And if ordering is reached, how many according to an exponential distribution, so that the average moving attempts are globally necessary? These are the sort of frequency is the sum of the action rates. This technique is again questions that could be addressed at the early stages of design, a generalisation of the one adopted in the SPIM simulation thanks to a simulation tool. engine for stochastic π-Calculus [6]. For a detailed description of the simulation framework, refer to [14]. IV. THE C OLLECTIVE S ORTING IN M AUDE In this section we briefly describe a M AUDE specification B. The Collective Sorting model of our solution to the collective sorting problem, and show The M AUDE specification of the Collective Sorting simulation results. Our model sticks to the case where 4 tuple system is divided in three modules, respectively defining 175 mod CS is pr CS . pr STANDARD-CARRIER . op source : Nat -> Action . *** SYNTAX OF ACTIONS AND STATES op chooseTarget : -> Action . op chooseTupleType : -> Action . op readSource : -> Action . op readTarget : -> Action . op move : -> Action . subsort DataSpace < State . *** A REFERNCE INITIAL STATE op SS : -> State . eq SS = ( init | < 0 @ (’a[100])|(’b[100])|(’c[10])|(’d[10]) > | < 1 @ (’a[ 0])|(’b[100])|(’c[10])|(’d[10]) > | < 2 @ (’a[ 10])|(’b[ 50])|(’c[50])|(’d[10]) > | < 3 @ (’a[ 50])|(’b[ 10])|(’c[10])|(’d[50]) > | (’a , ’b , ’c , ’d ) ) . *** IDENTIFYING SOURCE *** TRANSITION SYSTEM SEMANTICS eq (init | DS)==> = ( source(0) # 0.25 -> [ [0] | DS ] ); ( source(1) # 0.25 -> [ [1] | DS ] ); ( source(2) # 0.25 -> [ [2] | DS ] ); ( source(3) # 0.25 -> [ [3] | DS ] ) . *** CHOOSING TARGET eq ([Ns] | DS) ==> = (chooseTarget # now -> [ [Ns];[range(3)]| DS ]) . eq ([Ns];[Ns] | DS) ==> = (chooseTarget # now -> [ [Ns];[3] | DS ]) . *** CHOOSING TUPLE TYPE QQ ceq ([Ns];[Nt] | < Ns @ MT > | DS ) ==> = ( chooseTupleType # now -> [ ([Ns];[Nt];[QQ] | < Ns @ MT > | DS ) ] ) if QQ := choose(occurringTuples(MT)) . *** READING FROM SOURCE ceq ([Ns];[Nt];[Q] | < Ns @ MT > | QL | DS ) ==> = ( readSource # now -> [ ([Ns];[Nt];[Q];[QQ] | < Ns @ MT > | QL | DS ) ] ) if QQ := get( QL , sample(quantities(QL, MT))) . *** READING FROM TARGET ceq ([Ns];[Nt];[Q];[Q1] | < Nt @ MT > | QL | DS ) ==> = ( readTarget # now -> [ ([Ns];[Nt];[Q];[Q1];[QQ] | < Nt @ MT > | QL | DS ) ] ) if QQ := get( QL , sample (quantities(QL, MT))) . *** MOVING OR DISCARDING ceq ( [Ns];[Nt];[Q];[Q1];[Q] | < Ns @ (Q[s N ]) | MT > | < Nt @ (Q[ N’ ]) | MT1 > | DS ) ==> = ( move # now -> [ ( init | < Ns @ (Q[ N ]) | MT > | < Nt @ (Q[s N’]) | MT1 > | DS) ] ) if Q1 =/= Q . eq ( [Ns];[Nt];[Q];[Q1];[Q2] | DS ) ==> = ( move # now -> [ ( init | DS ) ] ) [owise] . eq temp( init | DS ) = false . *** TEMPORANEOUS STATES eq temp( DS ) = true [owise] . endm Fig. 2. The transition system semantics in module CS. the structure of a system state (CS-TYPES), some utility choose takes a list of tuple type identifiers and returns one functions (CS-FUNCTIONS), and finally the stochastic non-deterministically chosen; occurringTuples takes the transition system operator ==> (CS). Module CS-TYPES content of a tuple space and returns the list of tuple types and module CS-FUNCTIONS are not reported for brevity. occurring in it; quantities takes the content of a tuple Module CS-TYPES specifies the necessary types to define space and a list of tuple types and returns the cardinality of the structure of a system state. In particular, sort Tuple is each of them. used to model the occurrence of a tuple in a tuple space: for instance, ’a[10] means 10 tuples of tuple type ’a The CS module, as depicted in Figure 2, can be viewed occur. Sort Space is used to represent a tuple space: as the core of the Collective Sorting model. First of all, <0 @ (’a[10])|(’b[10])|(’c[10])|(’d[10])> six kinds of action are defined: the former is of the kind means the tuple space with identifier 0 has 10 copies of each source(0),. . . ,source(3) and is used to start an agent tuple type. Module CS-FUNCTIONS defines three functions: working on a certain tuple space; the others are constants corresponding to the five steps of the agent agenda. The 176 constant SS is assigned to the initial state of the system we want to simulate, where tuples are spread in different quantities 300 TS1-TT1 in the various tuple spaces. TS2-TT2 TS3-TT3 The stochastic transition system semantics is divided in six 250 TS4-TT4 groups according to the actions to be executed. Initially, four Number of Tuples actions of the first kind are allowed, each with rate 0.25. The 200 rate of other actions is the constant now, which is assigned to a large float, meaning that these actions should happen 150 immediately. By this modelling choice, we will simulate a system where one agent evaluates for moving a tuple at each 100 time unit, and such an evalution is immediate. The behaviour of transitions is briefly described as follows. 50 0 1000 2000 3000 4000 5000 a) source(i): When task init occurs in the space Time it is time to spawn a new agent task: any of the tuple spaces can be chosen as source, with same probability. Task [i] correspondingly replaces init, where i is the source chosen. Fig. 4. Dynamics of the winning tuple in each tuple space: notice that each Note that DS is a variable over DataSpace, which here tuple aggregates in a different tuples space. matches with the rest of the system. b) chooseTarget: To choose a target, any tuple space in 0,1,2 is tried. If the result is equal to the current source, of Figure 2, and represents a possible initial (disordered) tuple space 3 is actually taken as target. This guarantees configuration of tuples. Figure 3 shows a piece of the output the source and target tuple spaces to be distinct. The task produced by the execution of the simulation—where each moves then to state [Ns];[Nt]—source and target identifier, step includes simulation countdown counter, system state, and respectively. elapsed time. After some steps, some tuple starts moving from c) chooseTupleType: A tuple type is chosen ran- one space to the others. After 2024 time units, for instance, domly out of those currently occurring in Ns. This is computed tuple kind ’c is already completely collected in tuple space with functions choose and occurringTuple, and is used 2. After 4600 time units, the system converged to complete to avoid picking a tuple which is currently absent in the source sorting, as we expected from our distributed algorithm. Chart tuple space. The task moves then to [Ns];[Nt];[QQ]— in Figure 4 reports the dynamics of the winning tuple in each where QQ is the tuple type chosen. tuple space, showing e.g. that complete sorting is reached at d) readSource: In this step a tuple type is drawn different times in each case. The chart in Figure 5 displays from the source tuple space using uniform read. Expression instead the evolution of the tuple space 0: notice that only the get(QL,sample(quantities(QL, MT))) is used to tuple kind ’a aggregates here despite its initial concentration sample a tuple giving higher probability to those that occur was the same of tuple kind ’b. more. Although it would be possible to make some prediction, we e) readTarget: Similar sampling is done do not know in general which tuple space will host a specific on the target tuple space. The task moves now to tuple kind at the end of sorting: this is an emergent property [Ns];[Nt];[Q];[Q1];[Q2], where Q1 and Q2 are of the system and is the very result of the interaction of the the tuple types read. tuple spaces through the agents! Indeed, the final result is not f) move: If the task matches completely random and the concentration of tuples will evolve [Ns];[Nt];[Q];[Q1];[Q] and Q1 is different from Q, in the same direction most of the times. It is interesting to then a tuple of kind Q is to be moved from Ns to Nt, which analyse the trend of the entropy of each tuple space as a way is realised by properly updating the tuple counters. Otherwise to estimate the degree of order in the system through a single ([owise]), the tuple spaces state is left unchanged. In both value: since the strategy we simulate is trying to increase the cases, the task gets back to init. inner order of the system we expect the entropy to decrease, Finally, the temp function defines as temporary states those as actually shown in Figure 6. that do not have task init, which will then cause the D. Adding a Load-Balancing Case simulation counter not to update. The basic strategy based on constant rates (see Section IV- C. Simulating the Collective Sorting B) is not very efficient, since agents are assigned to a certain The simulation can be run by giving the M AUDE interpreter tuple space also if the tuple space is already ordered! We a command like may exploit this otherwise wasted computation by assigning idle agents to disordered tuple spaces, or rather to change the rewrite < [ 5000 : ( SS ) @ 0.0 ] > . working rates of agents. This alternative therefore looks suited which executes precisely 5000 agent executions starting from to realize a strategy to quicker reach the complete order of state SS. Such a state is defined as a constant in the code tuple spaces. 177 < [5000 : init | < 0 @ (’a[100]) | (’b[100]) | (’c[10]) | (’d[10]) > | < 1 @ (’a[0]) | (’b[100]) | (’c[10]) | (’d[10]) > | < 2 @ (’a[10]) | (’b[50]) | (’c[50]) | (’d[10]) > | < 3 @ (’a[50]) | (’b[10]) | (’c[10]) | (’d[50]) > | ’a,’b,’c,’d @ 0.0], ... [4000 : init | < 0 @ (’a[107]) | (’b[89]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[0]) | (’b[136]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[35]) | (’c[80]) | (’d[0]) > | < 3 @ (’a[53]) | (’b[0]) | (’c[0]) | (’d[80]) > | ’a,’b,’c,’d @ 9.7664497212663287e+2], ... [2000 : init | < 0 @ (’a[127]) | (’b[50]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[0]) | (’b[210]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[0]) | (’c[80]) | (’d[0]) > | < 3 @ (’a[33]) | (’b[0]) | (’c[0]) | (’d[80]) > | ’a,’b,’c,’d @ 3.0679938546387184e+3], ... [1000 : init | < 0 @ (’a[142]) | (’b[18]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[0]) | (’b[242]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[0]) | (’c[80]) | (’d[0]) > | < 3 @ (’a[18]) | (’b[0]) | (’c[0]) | (’d[80]) > | ’a,’b,’c,’d @ 4.0271359303450395e+3], ... [438 : init | < 0 @ (’a[160]) | (’b[0]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[0]) | (’b[260]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[0]) | (’c[80]) | (’d[0]) > | < 3 @ (’a[0]) | (’b[0]) | (’c[0]) | (’d[80]) > | ’a,’b,’c,’d @ 4.6001450653146167e+3], ... [0 : init | < 0 @ (’a[160]) | (’b[0]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[0]) | (’b[260]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[0]) | (’c[80]) | (’d[0]) > | < 3 @ (’a[0]) | (’b[0]) | (’c[0]) | (’d[80]) > | ’a,’b,’c,’d @ 5.0313233386068514e+3] > Fig. 3. Result for the Collective Sorting simulation 160 0.9 Tuple Space 1 140 0.8 Tuple Space 2 Tuple Space 3 120 0.7 Tuple Space 4 Number of Tuples 100 0.6 80 Entropy 0.5 60 0.4 40 0.3 20 0.2 0 0 1000 2000 3000 4000 5000 0.1 Time 0 0 1000 2000 3000 4000 5000 Tuple Template 1 Tuple Template 3 Tuple Template 2 Tuple Template 4 Time Fig. 5. Dynamic of tuple space 0: notice that only one kind of tuple Fig. 6. Entropy of tuple spaces: they all eventually reach 0, that is, complete aggregates here. order. In order to adapt the agents rate we need a measure of and it is easy to notice that 0 ≤ Hij ≤ k1 log2 k. We want to order: as already stated in Section III, spatial entropy may be express now the entropy associated with a single tuple space an effective measure for system order. If we denote with qij the amount of tuples of the kind i within the tuple space j, Pk nj the total number of tuples within the tuple space j, and k i=1 Hij Hj = (3) the number of tuple kinds, then, the entropy associated with log2 k the tuple kind i within the tuple space j is qij nj where the division by log2 k is introduced in order to obtain Hij = log2 (2) nj qij 0 ≤ Hj ≤ 1. If we have t tuple spaces then the entropy of the 178 system is t 1X 0.9 H= Hj (4) Tuple Space 1 t j=1 0.8 Tuple Space 2 Tuple Space 3 0.7 Tuple Space 4 where the division by t is used to normalize H, so that 0.6 0 ≤ H ≤ 1. Being t the number of tuple spaces then it also Entropy 0.5 represents the number of agents: let each agent work at rate Hj r, and tr be the maximum rate allocated to the sorting task. 0.4 If we want to adapt the working rates of agents we have to 0.3 scale their rate by the total system entropy, since 0.2 t 0.1 X t 1 γ rHj = tr ⇒ γ = Pt = (5) 0 j=1 j=1 Hj H 0 1000 2000 3000 4000 5000 Time rH hence each agent will work at rate H j where Hj and H are computed periodically. In order to modify the Collective Sorting model of Figure Fig. 7. Entropy of tuple spaces in the variable rate case: the system reaches 2, we replaced the constant agents rate of the first four action the complete order since step 3000. (refer to Section IV-B) with the Equation 3 : hence, the activity rate of the tuple space j becomes Hj instead of 0.25. Using load balancing we introduced dynamism in our model: indeed 0.7 Constant Rate in each simulation step the activity rate associated with a tuple Variable Rate 0.6 space—i.e. the probability at a given step that an agent of the tuple space is working—is no longer fixed, but it depends 0.5 on the entropy of the tuple space itself. Hence, as explained Entropy above, agents belonging to completely ordered tuple spaces 0.4 can consider their goal as being achieved, and hence they 0.3 no longer execute tasks. Moreover, this strategy guarantees a better efficiency in the load balancing of agents work: agents 0.2 working on tuple spaces with higher entropy, have a greater 0.1 activity rate than the others on more ordered tuple spaces. Using the Collective Sorting specification with variable 0 0 1000 2000 3000 4000 5000 rates, we ran the same simulation of the Section IV-C: the chart Time of Figure 7 shows the trend of the entropy of each tuple space. Comparing the chart with the one in Figure 6, we can observe that the entropies reach 0 faster than the case with constant Fig. 8. Comparison of global entropy in the case of constant and variable rates: indeed since step 3000 every entropy within the chart rate: the latter reaches the complete order quicker. in Figure 7 is 0, while with constant rates the same result is reached only after 4600 steps. The chart in Figure 8 compares the tendency of the global entropy (see Equation 5) in the case • In the context of collective sorting, we plan to evaluate of constant and variable rates: the trend of the two entropies other load-balancing approaches, optimising the conver- represents a further proof that variable rates guarantee a faster gence to complete order, and working with different stabilization of the system, i.e. its complete order. combinations of the number of tuple spaces and tuple kinds. V. C ONCLUSION AND F UTURE W ORKS • The library itself is currently a very simple prototype, In this article we argued about the necessity of consider- but we believe it could be improved in several ways and ing stochastic aspects when designing emergent coordination become a very practical simulation tool. mechanisms: this issue is both emerging in few proposals • Another interesting idea would be to apply our library to of new coordination models and in related research contexts. some existing coordination models like SwarmLinda, and We evaluated these ideas by using the M AUDE library we provide the necessary tests for the proposed algorithms. developed, considering and simulating a typical scenario of swarm-like coordination, the collective sorting problem, which R EFERENCES we believe is a very paradigmatic application of emergent [1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From coordination because of its basic formulation. Natural to Artificial Systems, ser. Santa Fe Institute Studies in the Several interesting future works can be pursued: Sciences of Complexity. Oxford University Press, Inc., 1999. 179 [2] L. Gardelli, M. Viroli, and A. Omicini, “On the role of simulations in engineering self-organising MAS: The case of an intrusion detection system in TuCSoN,” in Engineering Self-Organising Systems, ser. LNAI, S. A. Brueckner, G. Di Marzo Serugendo, D. Hales, and F. Zambonelli, Eds. Springer, 2006, vol. 3910, pp. 153–168, 3rd International Work- shop (ESOA 2005), Utrecht, The Netherlands, 26 July 2005. Revised Selected Papers. [3] M. Mamei and F. Zambonelli, “Programming pervasive and mobile com- puting applications with the tota middleware,” in Pervasive Computing and Communications, 2004. PerCom 2004. Proceedings of the Second IEEE Annual Conference on. IEEE, March 2004, pp. 263– 273. [4] R. Menezes and R. Tolksdorf, “Adaptiveness in linda-based coordina- tion models,” in Engineering Self-Organising Systems: Nature-Inspired Approaches to Software Engineering, ser. LNAI, G. D. M. Serugendo, A. Karageorgos, O. F. Rana, and F. Zambonelli, Eds. Springer Berlin / Heidelberg, January 2004, vol. 2977, pp. 212–232. [5] R. D. Nicola, D. Latella, and M. Massink, “Formal modeling and quantitative analysis of K LAIM-based mobile systems,” in SAC ’05: Proceedings of the 2005 ACM symposium on Applied computing. New York, NY, USA: ACM Press, 2005, pp. 428–435. [6] A. Phillips, “The Stochastic Pi Machine (SPiM),” 2006, version 0.042 available online at http://www.doc.ic.ac.uk/˜anp/spim/. [Online]. Available: http://www.doc.ic.ac.uk/ anp/spim/ [7] “Swarm,” 2006, available online at http://www.swarm.org/. [8] “Recursive porous agent simulation toolkit (repast),” 2006, available online at http://repast.sourceforge.net/. [9] M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martı́-Oliet, J. Meseguer, and C. Talcott, Maude Manual, 2nd ed., Department of Computer Science University of Illinois at Urbana-Champaign, December 2005, version 2.2 is available online at http://maude.cs.uiuc.edu. [10] C. Priami, “Stochastic pi-calculus,” The Computer Journal, vol. 38, no. 7, pp. 578–589, 1995. [11] H. Gutowitz, “Complexity-seeking ants,” in Proceedings of the Third European Conference on Artificial Life, Deneubourg and Goss, Eds., 1993. [12] K. Hadeli, P. Valckenaers, C. B. Zamfirescu, H. V. Brussel, B. S. Germain, T. Holvoet, and E. Steegmans, “Self-organising in multi- agent coordination and control using stigmergy,” in Engineering Self- Organising Systems: Nature-Inspired Approaches to Software Engineer- ing, ser. LNAI, G. D. M. Serugendo, A. Karageorgos, O. F. Rana, and F. Zambonelli, Eds. Springer Berlin / Heidelberg, January 2004, vol. 2977, pp. 105–123. [13] A. Omicini and E. Denti, “From tuple spaces to tuple centres,” Science of Computer Programming, vol. 41, no. 3, pp. 277–294, Nov. 2001. [14] M. Casadei, L. Gardelli, and M. Viroli, “Simulating emergent properties of coordination in maude: the collective sorting case,” in 5th Interna- tional Workshop on the Foundations of Coordination Languages and Software Architectures, Bonn, Germany, August 2006, to appear into. 180