Fast counting with the optimum combining tree
Roger P. Wattenhofer, Peter Widmayer · 1998
A distributed counter is a concurrent object which provides a test-and-incrementoperation on a shared value. On the basis of a distributed counter, one can implement various fundamental data structures, such as queues or stacks. We present a fast, linearizable counting scheme for processors that increment at arbitrary rates. Our counter is efficient in both, a message passing and a shared memory environment; we describe in detail the former. We analyze the expected behaviour of our scheme using queueing theory. In our simulations, we compare our scheme with Counting Networks and Diffracting Trees. 1 The Problem We observe an ever increasing importance of distributed data in our network-centric universe. Even though data is distributed over several processors, any processor should be able to access data at any time. Such an access may be triggered either by a human user or a running application program. The design and analysis of distributed data structures draws theoretical interest f...