PIMS CRG Distinguished Speaker: Faith Ellen
- Date: 12/05/2012
- Time: 11:00
University of British Columbia
Faster than Optimal Snapshots (for a While)
An atomic snapshot is a fundamental data structure for shared memorydistributed computation. It allows processes to scan and update ashared 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.
Part of a series from the PIMS CRG: Algorithmic Theory of Networks