On the Collective Sort Problem for Distributed Tuple Spaces

Matteo Casadei, Mirko Viroli, Luca Gardelli

Science of Computer Programming 74(9), pages 702-722

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

Journals & Series


— authors

— editors

Ernesto Pimentel, Jean-Marie Jacquet

— status


— sort

article in journal

— publication date


— journal

Science of Computer Programming

— volume

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

— volume


— issue


— pages



original page




— print ISSN


Partita IVA: 01131710376 — Copyright © 2008–2023 APICe@DISI – PRIVACY