BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2006-578
ENTRY:: June 12, 2006
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Wait-Free and Obstruction-Free Snapshot
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Do Ba, Khanh
DATE:: June 2006
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2006-578.pdf
ABSTRACT:: 
 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.
NOTE:: 
Senior Honors Thesis. Advisor: Prasad Jayanti.
END:: ncstrl.dartmouthcs//TR2006-578