James Aspnes and Keren Censor. Approximate shared-memory counting despite a strong adversary. ACM Transactions on Algorithms 6(2):1–23, March 2010 (SODA 2009 special issue). An earlier version appeared in Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2009, pp. 441–450.
A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n-1 crash failures. 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 counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes.
An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.
@article{AspnesC2010,
author = {Aspnes, James and Censor, Keren},
title = {Approximate shared-memory counting despite a strong adversary},
journal = {ACM Transactions on Algorithms},
volume = {6},
number = {2},
year = {2010},
issn = {1549-6325},
pages = {1--23},
doi = {https://doi.acm.org/10.1145/1721837.1721841},
publisher = {ACM},
address = {New York, NY, USA},
}