A Tight Time Bound for Distributed Counting
Counting is a well-studied distributed problem. It is central to many basic distributed coordination problems. Some examples are dynamic load-balancing, queues and barrier synchronization.
Many attempts have been made to devise efficient distributed algorithms for counting. For all known algorithms, the time taken to read and increment the counter is at least $n$ in the worst case, where $n$ is the number of processes that share the counter. Time includes both the number of accesses to shared memory and waiting caused by contention with other processes that are accessing the same memory location at the same time.
In this talk we present two lower bound results for implementations of distributed counters. Both lower bounds are for general classes of distributed objects that contain counters.
The first result, from 2002, was the first time lower bound for implementations of counters, stacks and queues that can use \emph{arbitrary} synchronization primitives. It establishes an $\Omega(\sqrt n)$ bound for implementations of these objects.
The second, recent, result proves a lower bound of $n$ on a somewhat more restricted set of objects. This lower bound matches the best algorithms for distributed counting and also holds for implementations that can use arbitrary synchronization primitives. The result implies that distributed counting is inherently sequential, at least in terms of worst case time complexity.
The presentation is for a general audience and no prior knowledge of distributed systems is assumed.
Joint work with Faith Ellen Fich and Nir Shavit.