A framework for modelling and implementing self-organising coordination

ABSTRACT

Research fields like pervasive computing are showing that the interactions between components in large-scale, mobile, and open systems are highly affected by unpredictability: self-organising techniques are increasingly adopted within infrastructures aimed at managing such interactions in a robust and adaptive way. Accordingly, in this paper we discuss the framework of self-organising coordination: coordination media spread over the network are in charge of managing interactions with each other and with agents solely according to local criteria, making interesting and fruitful global properties of the resulting system appearing by emergence---probability and timing typically playing a crucial role. We show that the TuCSoN coordination infrastructure can be used as a general platform for enacting self-organising coordination; we put it to test on two cases: an inter-space application of adaptive tuple clustering, and a intra-space application of chemical-like coordination reactions.

REFERENCES

• 1: Farhad Arbab, Reo: a channel-based coordination model for component composition, Mathematical Structures in Computer Science, v.14 n.3, p.329-366, June 2004 [doi>10.1017/S0960129504004153]
• 2: Gérard Berry , Gérard Boudol, The chemical abstract machine, Theoretical Computer Science, v.96 n.1, p.217-248, 6 April 1992
• 3: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 4: Jean-Pierre Bonâtre , Daniel Le Métayer, Gamma and the chemical reaction model: ten years after, Coordination programming: mechanisms, models and semantics, Imperial College Press, London, UK, 1996
• 5: M. Bravetti, R. Gorrieri, R. Lucchi, and G. Zavattaro. Probabilistic and prioritized data retrieval in the Linda coordination model. In Coordination Models and Languages, volume 2949 of LNCS, pages 55--70. Springer, 2004.
• 6: Mario Bravetti , Roberto Gorrieri , Roberto Lucchi , Gianluigi Zavattaro, Quantitative information in the tuple space coordination model, Theoretical Computer Science, v.346 n.1, p.28-57, 23 November 2005 [doi>10.1016/j.tcs.2005.08.004]
• 7: Scott Camazine , Nigel R. Franks , James Sneyd , Eric Bonabeau , Jean-Louis Deneubourg , Guy Theraula, Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ, 2001
• 8: Matteo Casadei , Luca Gardelli , Mirko Viroli, Simulating Emergent Properties of Coordination in Maude: the Collective Sort Case, Electronic Notes in Theoretical Computer Science (ENTCS), v.175 n.2, p.59-80, June, 2007 [doi>10.1016/j.entcs.2007.05.022]
• 9: Matteo Casadei , Andrea Omicini , Mirko Viroli, Prototyping A&A ReSpecT in Maude, Electronic Notes in Theoretical Computer Science (ENTCS), v.194 n.4, p.93-109, April, 2008 [doi>10.1016/j.entcs.2008.03.101]
• 10: Matteo Casadei , Mirko Viroli, Applying Self-Organizing Coordination to Emergent Tuple Organization in Distributed Networks, Proceedings of the 2008 Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems, p.213-222, October 20-24, 2008 [doi>10.1109/SASO.2008.18]
• 11: Rocco De Nicola , Diego Latella , Mieke Massink, Formal modeling and quantitative analysis of KLAIM-based mobile systems, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066777]
• 12: Simon Dobson , Spyros Denazis , Antonio Fernández , Dominique Gaïti , Erol Gelenbe , Fabio Massacci , Paddy Nixon , Fabrice Saffre , Nikita Schmidt , Franco Zambonelli, A survey of autonomic communications, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.1 n.2, p.223-259, December 2006 [doi>10.1145/1186778.1186782]
• 13: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 14: D. T. Gillespie. Exact stochastic simulation of coupled chemical reactions. The Journal of Physical Chemistry, 81(25): 2340--2361, 1977.
• 15: Owen Holland , Chris Melhuish, Stigmergy, self-organization, and sorting in collective robotics, Artificial Life, v.5 n.2, p.173-202, April 1999 [doi>10.1162/106454699568737]
• 16: Marco Mamei , Ronaldo Menezes , Robert Tolksdorf , Franco Zambonelli, Case studies for self-organization in computer science, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.8, p.443-460, August 2006 [doi>10.1016/j.sysarc.2006.02.002]
• 17: Marco Mamei , Franco Zambonelli, Programming Pervasive and Mobile Computing Applications with the TOTA Middleware, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.263, March 14-17, 2004
• 18: R. Menezes and R. Tolksdorf. Adaptiveness in Linda-based coordination models. In Engineering Self-Organising Systems: Nature-Inspired Approaches to Software Engineering, volume 2977 of LNAI, pages 212--232. Springer, 2004.
• 19: J. S. Nicolis, E. Protonotarios, and E. Lianos. Some views on the role of noise in "self"-organizing systems. Biological Cybernetics, 17(4): 183--193, 1975.
• 20: A. Omicini and E. Denti. From tuple spaces to tuple centres. Science of Computer Programming, 41(3): 277--294, Nov. 2001.
• 21: A. Omicini, A. Ricci, and M. Viroli. Time-aware coordination in ReSpecT. In J.-M. Jacquet and G. P. Picco, editors, Coordination Models and Languages, volume 3454 of LNCS, pages 268--282. Springer-Verlag, Apr. 2005.
• 22: Andrea Omicini , Alessandro Ricci , Mirko Viroli, Timed environment for web agents, Web Intelligence and Agent Systems, v.5 n.2, p.161-175, April 2007
• 23: Andrea Omicini , Alessandro Ricci , Mirko Viroli, Artifacts in the A&A meta-model for multi-agent systems, Autonomous Agents and Multi-Agent Systems, v.17 n.3, p.432-456, December 2008 [doi>10.1007/s10458-008-9053-x]
• 24: H. Van Dyke ParunaK , Sven Brueckner , John Sauter, Digital pheromone mechanisms for coordination of unmanned vehicles, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544843]
• 25: A. Phillips. The Stochastic Pi Machine (SPiM). http://research.microsoft.com/~aphillip/spim/.
• 26: C. Priami. Stochastic pi-calculus. The Computer Journal, 38(7): 578--589, 1995.
• 27: I. Prigogine and I. Steingers. The End of Certainty: Time, Chaos, and the New Laws of Nature. Free Press, 1997.
• 28: Franco Zambonelli , H. Van Dyke Parunak, Towards a paradigm change in computer science and software engineering: a synthesis, The Knowledge Engineering Review, v.18 n.4, p.329-342, December 2003 [doi>DOI:10.1017/S0269888904000104]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems; Coherence and coordination

Keywords:
A&A, ReSpecT, TuCSoN, chemical coordination, self-organising coordination, tuple clustering