Speaker: Danny Hendler, Technion

Time: Thursday, April 6, 2006, 10:30.

----------------------------------------------------------------------
Title: A Tight Time Lower Bound for Distributed Counting and Related
Problems
----------------------------------------------------------------------

Counting is a well-studied distributed problem. Its simple
formulation and the fact that it is the key to solving and designing
many other basic distributed coordination problems, such as dynamic
load-balancing, queues and barrier synchronization, drew the
attention of many researchers.

Specifically, many attempts have been made to devise efficient
distributed algorithms for counting in shared-memory systems. In
these systems processes communicate with each other by applying
synchronization primitives such as read, write, and
read-modify-write to shared variables.

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 variables and waiting caused by contention
with other processes that are accessing the same variable at the
same time.

In this talk we present two lower bound results that apply for
general classes of distributed objects. Both these classes contain
counters, stacks and queues.

The first result, from 2003, was the first time lower bound
on implementations of counters, stacks and queues that can use
\emph{arbitrary} synchronization primitives. It established an
$\Omega(\sqrt n)$ bound on implementations of these objects.

The second result, from 2005, proves a lower bound of $n$ on a
somewhat more restricted class of objects. This lower bound
matches the best algorithms for distributed counting and also
holds for implementations that can use arbitrary synchronization
primitives. Our result implies that distributed counting is
inherently sequential, at least in terms of worst case time
complexity.

The presentation is for a general audience. No prior knowledge
of distributed systems is assumed.


Joint work with Faith Ellen Fich and Nir Shavit.