UTCS Colloquia - Algorithms and Computation Theory - Faith Ellen, University of Toronto, "Faster Than Optimal Snapshots (for a While)" GDC 4.516

Contact Name: 
Vijaya Ramachandran
GDC 4.516
Apr 10, 2013 2:00pm - 3:30pm

Signup Schedule: http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Host:  Vijaya Ramachandran

Talk 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.