February 22, Tuesday
12:00 – 14:00
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 2002, was the first time lower bound for implementations of counters, stacks and queues that can use 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
http://www.cs.toronto.edu/~hendler/
Short Bio:
Danny Hendler is a post-doctoral fellow in the University of Toronto. Since being released from the IDF in 1983, he has been working in the Israeli high-tech industry, serving in both technical and managerial positions in companies such as Elscint, Telrad, National Seminconductor and Sun Microsystems. In 2001 he returned to Academy to pursue his Ph.D. in Tel-Aviv University under the supervision of Prof. Nir Shavit. His current research focuses on lower bounds and algorithms for distributed systems and dynamic load balancing.