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.

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.