We present a simple and efficient self-stabilizing protocol for the network partitioning problem. Given a graph with k~2 nodes, our decomposition scheme partitions the network into connected and disjoint partitions, with k nodes per partition. The proposed algorithm starts with a spanning tree of the graph, but uses some links which do not belong to the tree, if necessary. The protocol stabilizes in (3h+1) steps, where h is the height of the tree, and adapts to the dynamic configuration of the network.
展开▼
