Wait-Free and Obstruction-Free Snapshot
Khanh Do Ba, Prasad Jayanti · 2006
The snapshot problem was first proposed over a decade ago [1, 2] and has since been well-studied in the distributed algorithms community [4, 5, 6, 7, 8, 9, 12, 13, 14, 17, 18]. 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 ith 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 [10]. First, we present a simple, time and space optimal, obstruction-free solution to the singlewriter, 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(mn2) of the only previously known time-optimal solution [14]. Snapshot algorithm Primitive used Update time Scan time Space This paper CAS or LL/SC O(1) O(m) O(mn) Afek et al. [1] read/write O(mn) O(mn) O(mn+ n) Anderson [2] read/write O(2) O(2) O(mn log n) Haldar and Vidyasankar [9] read/write O(mn) O(mn) O(mn) Jayanti [13] CAS or LL/SC O(m) O(m) O(mn) Jayanti [14] CAS or LL/SC O(1) O(m) O(mn) Table 1: Comparison of multi-writer snapshot algorithms. Snapshot algorithm Primitive used Update time Scan time Space Afek et al. [1] read/write O(n) O(n) O(n) Anderson [2] read/write O(2) O(2) O(n log n) Aspnes and Herlihy [4] read/write O(n) O(n) O(n) Attiya et al. [5] test&set O(n) O(n) ∞ Attiya and Rachman [6], read/write O(n log n) O(n log n) ∞ uses unbounded registers Chandra and Dwork [7] CAS or LL/SC O(n) O(n) ∞ Dwork et al. [8], weak snapshot read/write O(n) O(n) O(n) Haldar and Vidyasankar [9] read/write O(n) O(n) O(n) Israeli et al. [12] read/write O(n) O(n log n) O(n) Kirousis et al. [17], single-scanner read/write O(1) O(n) O(n) Riany et al. [18] CAS or LL/SC, O(1) O(n) O(n) and fetch&inc Table 2: Comparison of single-writer snapshot algorithms.