On the Collective Sort Problem for Distributed Tuple Spaces

Matteo Casadei, Mirko Viroli, Luca Gardelli

In systems coordinated with a distributed set of tuple spaces, it is crucial to make agents easily retrieving the tuples they are interested in. This can be achieved by some sorting technique that can group similar tuples together in the same tuple space, so that the position of a tuple can be inferred by similarity. Accordingly, we formulate the col lective sort problem for distributed tuple spaces, where an on-line, background service of autonomous agents is in charge of moving tuples from one space to the other until reaching complete sorting, namely, each of the N tuple spaces aggregate tuples belonging to one of the N kinds available. After pointing out the requirements for effectively tackling this problem, we propose a self-organising solution inspired by ants' brood sorting. This is based on simple agents that perform partial observations and accordingly take decisions on tuple movement.
Complete convergence from any initial configuration of tuples is addressed by a form of fully-adaptive simulated annealing, based on noise tuples inserted and removed by agents on a by-need basis so as to avoid situations of non-optimal sorting. The approach is evaluated by stochastic simulations, which provide evidence of full-sorting emergence, scalability, and reactiveness to external interactions. 

(keywords) Self-Organising Systems, Tuple Spaces, Stochastic Simulations, Collective Sort

Science of Computer Programming 74(9), pages 702-722,  2009.
Ernesto Pimentel, Jean-Marie Jacquet (eds.), Elsevier Science B. V..

Author = {Casadei, Matteo and Viroli, Mirko and Gardelli, Luca},
Booktitle = {Special Issue on the 5th International Workshop on Foundations of Coordination Languages and Architectures (FOCLASA '06)},
Doi = {10.1016/j.scico.2008.09.018},
Editor = {Pimentel, Ernesto and Jacquet, Jean-Marie},
Issn = {0167-6423},
Journal = {Science of Computer Programming},
Keywords = {Self-Organising Systems, Tuple Spaces, Stochastic Simulations, Collective Sort},
Number = 9,
Pages = {702--722},
Publisher = {Elsevier Science B. V.},
Title = {On the Collective Sort Problem for Distributed Tuple Spaces},
Url = {http://www.sciencedirect.com/science/article/pii/S0167642309000318},
Volume = 74,
Year = 2009}

Journals & Series

Partita IVA: 01131710376 - Copyright © 2008-2021 APICe@DISI Research Group - PRIVACY