PIMS CRG Distinguished Speaker: Faith Ellen

  • Date: 12/05/2012
  • Time: 11:00
Faith Ellen, University of Toronto

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.

Other Information: 

Location: ICCSX836


Part of a series from the PIMS CRG: Algorithmic Theory of Networks