Abstract:

 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 & 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 2003, was the first time lower bound
 for implementations of counters, stacks and queues that can use
 \emph{arbitrary} synchronization primitives. It established 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 presentation is for a general audience. No prior knowledge
 of distributed systems is assumed.


 Joint work with Faith Ellen Fich and Nir Shavit.