Counting Networks

A library of lock-free data structures for concurrent counting.

Usage

extern crate counting_networks;

use counting_networks::counters::{Counter, BitonicCountingNetwork};

License

counting-networks is primarily distributed under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, and LICENSE-MIT for details.

lib.rs:

A counting network is a type of concurrent data structure that gives non-blocking access to specific operations, most commonly fetch-and-inc.

They were first introduced in a paper by James Aspnes, Maruice Herlihy, and Nir Shavit [1].

Construction

Counting networks are from simple components called balancers. A balancer can be visualized as a element that takes two input wires and produces two output wires. Threads moving through the structure can be represented as tokens that pass along these wires. Balancers will alternate sending tokens arriving on input wires to either the top output wire or the bottom output wire. This ensures that the arriving tokens are distributed in a balanced way across the outputs.

For example (where the number indicates the order that the tokens enter):

7 6 4 2 1 ──╥── 1 3 5 7
      5 3 ──╨── 2 4 6

Counting networks are a subclass of a broader type of network called a balancer network that are built using these elements. A balancer (and balancing networks in general), will ensure that the difference in the number of tokens between each pair of wires is bounded. They are also known as k-smoothing networks, where k is the bound [2]. Counting networks are equivalent to 1-smoothing networks, where the difference in outputs along each wire will always be 1. Another property of counting networks is that they will always output tokens in increasing order modulo the size of the network.

A larger example illustrating this:

      ─────╥────╥─────╥─── 1 5
4 3 1 ─────╨────║──╥──╨─── 2 6
5     ─────╥────║──╨──╥─── 3 7
7 6 2 ─────╨────╨─────╨─── 4

This can be applied to implement a shared counter, a data structure that provides fetch-and-inc operations, by attaching a local counter to each output wire so that every token leaving the network will take the value of the counter and increment it by the width of the network. The i^th wire will have counter c_i that initially contains value i. If w is the output width of the network, the local counter will emit the values i, i + w, i + 2w, i + 3w, ...

Papers

Read the paper by Aspnes et al. as an introduction to the subject. There is also a portion of a textbook that gives a lovely overview of concurrent data structures and where counting networks fit in. Look for the section on Fetch-and-φ Structures. Another paper gives the larger context of balancing/smoothing networks. Lastly the Wikipedia page on sorting networks is fairly intuitive, and you can see how they relate to the other types of networks.