On the Collective Sort Problem for Distributed Tuple Spaces


Matteo Casadei, Mirko Viroli, Luca Gardelli

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

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

— journal

Science of Computer Programming

— volume

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

— volume

74

— issue

9

— pages

702-722

— publication date

2009

URLs

original page

Identifiers

— 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-2022 APICe@DISI Research Group - PRIVACY