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..

@article{collectivesort-scp74,
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

Publication

— authors

Matteo Casadei, Mirko Viroli, Luca Gardelli

— editors

Ernesto Pimentel, Jean-Marie Jacquet

— status

published

— sort

article in journal

Venue

— volume

Special Issue on the 5th International Workshop on Foundations of Coordination Languages and Architectures (FOCLASA '06)

— publication date

2009

— pages

702-722

— journal

Science of Computer Programming

— volume/issue

74 (9)

— publication date

2009

— pages

702-722

URLs & IDs

original page

— DOI

10.1016/j.scico.2008.09.018

— print ISSN

0167-6423

BibTeX

— BibTeX ID
collectivesort-scp74
— BibTeX category
article

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