A Self-Organising Solution to the Collective Sort Problem in Distributed Tuple Spaces

   page       BibTeX_logo.png   
Mirko Viroli, Matteo Casadei, Luca Gardelli
Alessandro Ricci, Michael Schumacher, Bernard Angerer (eds.)
SAC '07: Proceedings of the 2007 ACM Symposium on Applied Computing, pages 354-359
ACM , New York, NY, USA

Coordination languages and models are recently moving towards the application of techniques coming from the research context of complex systems: adaptivity and self-organisation are exploited in order to tackle typical features of systems to coordinate, such as openness, dynamism and unpredictability. In this paper we focus on a paradigmatic problem we call collective sort, where autonomous agents are assigned the task of moving tuples across different tuple spaces with the goal of reaching perfect clustering: tuples of the same kind are to be collected in the same, unique tuple space. We describe a self-organising solution to this problem, where each agent moves tuples according to partial observations, still making complete sorting emerge from any initial tuple configuration.