.png){kind=icon}
.png){kind=icon}
Return
Self-stabilizing deterministic network decomposition
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.2001.1811.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is self-stabilizing meaning that starting from an arbitrary state, it is guaranteed to reach a state where the network is correctly partitioned. The protocol stabilizes in 3(h+1) rounds, where h is the height of the tree. We also propose solutions to the case where the network size is n not equal k(2). Hence our protocol works for dynamic systems in the sense that the protocol can adapt to changes of the network size. We discuss an important application of the proposed protocol. (C) 2002 Elsevier Science (USA).
Keywords:
network decomposition
quorum systems
self-stabilization
spanning tree
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available