The counting pyramid: an adaptive distributed counting scheme

✍ Scribed by Roger Wattenhofer; Peter Widmayer

• Book ID: 104344689
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 312 KB
• Volume: 64
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1016/s0743-7315(03)00114-x

✦ Synopsis

A distributed counter is a concurrent object which provides a fetch-and-increment operation 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 the counting pyramid, an efficient implementation of a distributed counter in a message passing system, which is based on software combining. The counting pyramid adapts gracefully to changing access patterns, guarantees linearizability, and offers more general fetch-and-F operations. We analyze the expected performance of the counting pyramid, using queueing theory and simulation. We show that the latency of the counting pyramid is asymptotically optimal.