%T Wait-Free and Obstruction-Free Snapshot
%A Khanh Do Ba
%R Technical Report TR2006-578
%I Dartmouth College, Computer Science
%C Hanover, NH
%D June 2006
%U http://www.cs.dartmouth.edu/reports/TR2006-578.pdf
%X
  The snapshot problem was first proposed over a decade ago and has 
 since been well-studied in the distributed algorithms community. The 
 challenge is to design a data structure consisting of $m$ components, 
 shared by upto $n$ concurrent processes, that supports two 
 operations. The first, $Update(i,v)$, atomically writes $v$ to the 
 $i$th component. The second, $Scan()$, returns an atomic snapshot of 
 all $m$ components. We consider two termination properties: 
 wait-freedom, which requires a process to always terminate in a 
 bounded number of its own steps, and the weaker obstruction-freedom, 
 which requires such termination only for processes that eventually 
 execute uninterrupted.
  First, we present a simple, time and space optimal, obstruction-free 
 solution to the single-writer, multi-scanner version of the snapshot 
 problem (wherein concurrent Updates never occur on the same 
 component). Second, we assume hardware support for compare&swap (CAS) 
 to give a time-optimal, wait-free solution to the multi-writer, 
 single-scanner snapshot problem (wherein concurrent Scans never 
 occur). This algorithm uses only $O(mn)$ space and has optimal CAS, 
 write and remote-reference complexities. Additionally, it can be 
 augmented to implement a general snapshot object with the same time 
 and space bounds, thus improving the space complexity of $O(mn^2)$ of 
 the only previously known time-optimal solution.
%Z
 Senior Honors Thesis. Advisor: Prasad Jayanti.