Counting networks are well studied parallel and distributed data structures, which are useful in synchronization applications such as distributed counting and load balancing. However, current constructions of counting networks are static, since their width (the degree of parallelism), and hence the size of the network, have to be fixed in advance. This present an obstacle in efficiently implementing them in a large distributed system whose size may be changing, due to nodes joining and leaving the network.
We present an adaptive construction of the bitonic counting network. Our network tunes its width to the system size in a distributed and local way.
With high probability, the effective "width" of the network is .(N/log² N), where N is the number of nodes currently in the system, and the effective "depth" of the network is O(log² N). In contrast, a static implementation would have the same width irrespective of the system size. When the system size changes, the network adapts by splitting or merging its components. All decisions and actions are decentralized: these include the decision of when to split and merge the components, and the action of splitting and merging them. Our construction is layered on an overlay network which provides an efficient peer-to-peer lookup service, and uses the recursive structure present in the bitonic network to adapt its implementation. Though we discuss the bitonic network, our technique could be applied to build an adaptive implementation of any distributed data structure which can be decomposed in a recursive way.
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb