CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Physarum-inspired self-biased walkers for distributed clustering

Devan Sohier ; Giorgos Georgiadis (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Simon Claviere ; Marina Papatriantafilou (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Alain Bui
Göteborg : Chalmers University of Technology, 2012. - 12 s.
[Rapport]

In this report, we propose a distributed scheme to compute distance-based clusters. We first present a mechanism based on the flow of distributed tokens called walkers, circulating randomly between a source and a sink to compute a shortest path. This mechanism is a discrete emulation of the slime mould (Physarum polycephalum) dynamics presented in [16]: each node observes the flow of walkers going through each adjacent edge and uses this flow to compute the probabilities with which it sends the walkers through each edge. Then, based on this mechanism, we show how several sources compute a shortest path DAG to a given sink. Finally, given some clusterheads acting like sinks, we prove that this process converges to distance-based clusters (i.e. nodes join the clusterhead to which they are closest) with shortest-path DAGs. The algorithm is designed with a special focus on dynamic networks: the ow locally adapts to the appearance and disappearance of links and nodes, including clusterheads.

Nyckelord: physarum, overlay networks, random walks, adaptive, distributed, clustering



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2012-08-22. Senast ändrad 2012-08-23.
CPL Pubid: 162439