An efficient counting network

We present a novel counting network construction, where the number of input wires w is smaller than or equal to the number of output wires t. The depth of our network is Θ ( lg 2 w ), which depends only on w. In contrast, the amortized contention of the network depends on the number of concurrent processes n and the parameters w and t. This offers more flexibility than all previously known networks, with the same number w of input and output wires, whose contention depends only on two parameters, w and n. In case n > w lg w, by choosing t > w lg w the contention of our network is O ( n lg w / w ), which improves by a logarithmic factor of w over all previously known networks with w wires.

Authors

• Costas Busch
• Marios Mavronicolas University of Cyprus

Keywords

• Counting network
• Balancing network
• Contention
• Shared memory
• Distributed data structure