Approximate Shared-Memory Counting Despite a Strong Adversary
Approximate Shared-Memory Counting Despite a Strong Adversary
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/∊)) …