A top-down algorithm for clustering in large-scale distributed networks

摘要

In this article, we propose a distributed top-down clustering algorithm for large-scale systems subject to topo-logical changes. The objective of this clustering is to divide large systems into smaller subsystems on which distributed algorithms can be executed efficiently. The main parameter of distributed algorithms complexity is the size of the system, which leads us to focus on bounded-size clusters. Top-down approach allows us to build a cluster naming from which we derive an efficient inter-cluster routing scheme. Clusters are built by a token moving from node to node according to a random walk scheme. When the cluster reaches a maximal size defined by a parameter K, it is divided (when possible) and tokens are created in both of the new clusters. The new clusters are then built and divided in the same fashion. A spanning tree is built during the construction. These spanning trees, together with the edges along which clusters have been divided, constitute a spanning tree of the system, which allows routing thanks to a consistent routing scheme. In a dynamic system, the clustering may be divided into two disjoint structures. This is also the case when multiple initiators begin the clustering process. When two structures meet, one is "adopted" by the other. This adoption mechanism allows the clustering to adopt transparently to topological changes