The counting pyramid
Roger P. Wattenhofer, Peter Widmayer · Repository for Publications and Research Data (ETH Zurich) · 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, the Counting Pyramid.We analyze the expected behaviour of the Counting Pyramid using queueing theory. The ProblemWe observe a n e v er increasing importance of distributed data in our interconnected world.Even though data is distributed over several processors, any processor should be able to access data quickly.Such an access may be triggered either by a h uman user or a running application program.The design and analysis of distributed data structures draws theoretical interest from the fact that, contrary to distributed algorithms, processors in distributed data structures generally compete against each other rather than co-operate: An operation triggered by processor p may i n terfere with an operation of processor q, and it may t h us make the work invested by q futile.