PIMS CRG Distinguished Speaker: Faith Ellen
Date
-
Topic
Faster than Optimal Snapshots (for a While)
Speakers
Details
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.
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.
Additional Information
Location: ICCSX836
Part of a series from the PIMS CRG: Algorithmic Theory of Networks
Faith Ellen, University of Toronto