Prasad Jayanti
ABSTRACT
An m-component, n-process snapshot object is an abstraction of shared memory that consists of m words and allows up to n processes to concurrently execute the following two types of operations: write(i,v), which writes v into the ith word, and scan(), which returns the current values of all m locations [1, 3]. The snapshot problem is to design algorithms for the write and scan operations that meet two challenging requirements: (1) operations appear to be atomic, and (2) operations are wait-freeFor any (m-component, n-process) snapshot algorithm, which runs on hardware that supports only word-sized objects, Ω(1) and Ω(m) are trivial lower bounds on the time complexity of write(i,v) and scan(), respectively. But, are these bounds tight?For a restricted version of the snapshot problem, known in the literature as the single-writer snapshot problem, Riany, Shavit and Touitou [18] showed that the answer is yes: they designed an algorithm with O(1) and O(m) running times for the write(i,v) and scan() operations, respectively. (The single-writer snapshot problem assumes that (i) the number m of words of the snapshot object is equal to the number n of processes, and (ii) only the ith process may write into the ith snapshot word.This paper shows that the same (optimal) running times of O(1) for write(i,v) and O(m) for scan() are achievable for the general problem, known in the literature as the multiwriter snapshot problem. Our algorithm requires hardware support for the CAS (compare&swap) operation (in comparison, Riany, Shavit and Touitou's algorithm requires hardware support for CAS, fetch&inc, and fetch&dec operations).
- Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. In Proceedings of the 9th Annual Symposium on Principles of Distributed Computing, pages 1--14, 1990. Google Scholar
Digital Library
- Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873--890, September 1993. Google ScholarDigital Library
- J. Anderson. Composite registers. In Proceedings of the 9th Annual Symposium on Principles of Distributed Computing, pages 15--29, 1990. Google ScholarDigital Library
- J. Anderson. Composite registers. Distributed Computing, 6(3):141--154, 1993. Google ScholarDigital Library
- J. Anderson. Multi-writer composite registers. Distributed Computing, 7(4):175--195, 1994. Google ScholarDigital Library
- J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In Proceedings of the 2nd Annual ACM Symposium on Parallel Architectures and Algorithms, pages 340--349, 1990. Google ScholarDigital Library
- H. Attiya, M. Herlihy, and O. Rachman. Efficient atomic snapshots using lattice agreement. In Proceedings of the 6th International Workshop on Distributed Algorithms, pages 35--53, 1992. Google ScholarDigital Library
- H. Attiya and O. Rachman. Atomic snapshots in o(n log n) operations. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, pages 29--40, 1993. Google ScholarDigital Library
- T. D. Chandra and C. Dwork. Using consensus to solve atomic snapshots. Unpublished manuscript, 1993.Google Scholar
- C. Dwork, M. P. Herlihy, S. Plotkin, and O. Waarts. Time lapse snapshots. In Proceedings of the Israel Symposium on the Theory of Computing and Systems, pages 154--170, May 1992. Google ScholarDigital Library
- S. Haldar and K. Vidyasankar. Elegant constructions of atomic snapshot variables. Technical Report Technical Report No: 9204, Memorial University of Newfoundland, Department of Computer Science, Memorial University of Newfoundland, St. John's, NF, Canada, A1C 5S7, May 1992.Google Scholar
- M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM TOPLAS, 12(3):463--492, 1990. Google ScholarDigital Library
- P. Jayanti. f-arrays: implementation and applications. In Proceedings of the 21st Annual Symposium on Principles of Distributed Computing, pages 270 -- 279, 2002. Google ScholarDigital Library
- P. Jayanti and S. Petrovic. Efficient and practical constructions of LL/SC variables. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing, July 2003. Google ScholarDigital Library
- P. Jayanti and S. Petrovic. Efficient wait-free implementation of multiword ll/sc variables. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS), June 2005. Google ScholarDigital Library
- L. Kirousis, P. Spirakis, and P. Tsigas. Reading many variables in one atomic operation: solutions with linear or sublinear complexity. In Proceedings of the 5th International Workshop on Distributed Algorithms, pages 229--241, 1991. Google ScholarDigital Library
- M. Moir. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pages 219--228, August 1997. Google ScholarDigital Library
- Y. Riany, N. Shavit, and D. Touitou. Towards a practical snapshot algorithm. Theoretical Computer Science, 269(1-2):163--201, 2001.Google ScholarCross Ref
Index Terms
- An optimal multi-writer snapshot algorithm
Recommendations
Partial snapshot objects
SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architecturesWe introduce a generalization of the atomic snapshot object, which we call the partial snapshot object. This object stores a vector of values. Processes may write components of the vector individually or atomically read any subset of the components. We ...
Single-scanner multi-writer snapshot implementations are fast!
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingSnapshot objects allow processes to obtain consistent global views of shared memory. A snapshot object consists of m components each capable of storing a value. The processes execute UPDATE operations to write new values in any of the components and ...
Brief Announcement: Non-blocking Dynamic Unbounded Graphs with Wait-Free Snapshot
Stabilization, Safety, and Security of Distributed SystemsAbstractIn this paper, we have implemented a dynamic unbounded concurrent graph which can perform the add, delete or lookup operations on vertices and edges concurrently and are linearizable. In addition to these operation s, we also have a wait-free ...
Comments