Low Contention Linearizable Counting

The linearizable counting problem requires asynchronous concurrent processes to assign themselves successive values so that the order of the values assigned reflects the real-time order in which they were requested. It is shown that the problem can be solved without funneling all processes through a common memory location. Two new constructions for linearizable counting networks, data structures that solve the linearizable counting problem, are given. The first construction is nonblocking: some process takes a value after O(n) network gates have been traversed. The second construction is wait-free: it guarantees that each process takes a value after it traverses O(wn) gates, where w is a parameter affecting contention. It is shown that in any nonblocking or wait-free linearizable counting network, processes must traverse an average of Omega (n) gates, and so the constructions are close to optimal. A simpler and more efficient network is constructed by giving up the robustness requirements and allowing processes to wait for one another. >

Authors

• Maurice Herlihy
• Nir Shavit
• Orli Waarts

Keywords

• Data structures
• Wires
• Contracts
• Heart
• Sorting
• Counting circuits
• Computer science
• Robustness
• Concurrent computing
• Hardware
• Linearizable
• Data Structure
• Lower Bound
• Infinity
• Less Than Or Equal
• Quiescent State
• Network State
• Average Path Length
• Top Line
• Infinite Sequence
• Lesser Value
• Induction Hypothesis
• Preferential Paths
• Elements AR
• Shared Memory
• Output Line
• Input Tokens
• Kinds Of Barriers
• Section Constructs