A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ε, the counter achieves a relative error of Δ with high probability, at the cost of O(((1/Δ) log n)O(1/ε)) register operations per increment and O(n4/5+ε((1/Δ) log n)O(1/ε)) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes.
展开▼
