Counting networks are practically linearizable

Counting networks are a class of concurrent structures that allow the design of highly scalable concurrent data structures in a way that eliminates sequential bottle-necks and contention. Linearizable counting networks assure that the order of the values returned by the network reflects the real-time order in which they were requested. We argue that in many concurrent systems the worst case scenarios that violate linearizability require a form of timing anomaly that is uncommon in practice. The linear time cost of designing networks that achieve linearizability under all circumstances may thus prove an unnecessary burden on applications that are willing to trade-off occasional non-linearizability for speed and parallelism. This paper presents a very simple measure that is local to the individual links and nodes of the network, and that quantifies the extent to which a network can suffer from timing anomalies and still remain linearizable. Perhaps counter-intuitively, this measure is independent of network depth. We use our measure to mathematically support our experimental results: that in a variety of normal situations tested on a simulated shared memory multiprocessor, the bitonic counting networks of Aspnes, Herlihy, and Shavit are 'for all practical purposes' linearizable.