PIMS Algorithmic Theory of Networks CRG Distinguished Lecture

Speaker: Faith Ellen, Department of Computer Science, University of Toronto

Homepage:  http://www.cs.toronto.edu/~faith/

Title: Faster than Optimal Snapshots (for a While)

Abstract:

An atomic snapshot is a fundamental data structure for shared memory distributed computation. It allows processes to scan and update a
shared array so that the operations seem to take effect atomically.
The worst case number of reads and writes to perform a snapshot operation
is $\Omega(n)$, where $n$ is the number of processes. This talk will
present an implementation of an atomic snapshot in which the number of
reads and writes per operation is in $O(\log^3 n)$, provided the number of
operations performed is polynomial in $n$.
(This work is joint with James Aspnes, Hagit Attiya, and Keren Censor-Hillel and appeared at PODC 2012.)

Host: David Kirkpatrick

Contact:  Holly Kwan (Tel: 2.3060)