James Aspnes
Hagit Attiya
Faith Ellen
Abstract
This article presents a novel implementation of a snapshot object for n processes, with O(log2 b log n) step complexity for update operations and O(log b) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes.
For polynomially many updates, this is an exponential improvement on previous snapshot algorithms, which have linear step complexity. It overcomes the existing Ω(n) lower bound on step complexity by having the step complexity depend on the number of updates. The key to this implementation is the construction of a new object consisting of a pair of max registers that supports a scan operation.
- Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. 1993. Atomic snapshots of shared memory. J. ACM 40, 4, 873--890. Google Scholar
Digital Library
- D. Alistarh, J. Aspnes, M. Bender, R. Gelashvili, and S. Gilbert. 2014. Dynamic task allocation in asynchronous shared memory. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 416--435. Google ScholarDigital Library
- J. H. Anderson. 1993. Composite Registers. Distrib. Comput. 6, 3, 141--154. Google ScholarDigital Library
- J. H. Anderson and Mark Moir. 1993. Towards a necessary and sufficient condition for wait-free synchronization. In Proceedings of the 7th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science, Vol. 725, Springer, 39--53. Google ScholarDigital Library
- J. H. Anderson and M. Moir. 1995. Universal Constructions for Large Objects. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science, vol. 972, Springer, 168--182. Google ScholarDigital Library
- J. Aspnes, H. Attiya, and K. Censor-Hillel. 2012a. Polylogarithmic concurrent data structures from monotone circuits. J. ACM 59, 1, 2:1--2:24. Google ScholarDigital Library
- J. Aspnes, H. Attiya, K. Censor-Hillel, and D. Hendler. 2012b. Lower bounds for resricted-use objects. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 172--181. Google ScholarDigital Library
- J. Aspnes and K. Censor. 2009. Approximate shared-memory counting despite a strong adversary. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09). SIAM Philadelphia, PA, 441--450. Google ScholarDigital Library
- J. Aspnes and M. Herlihy. 1990. Wait-free data structures in the asynchronous PRAM model. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 340--349. Google ScholarDigital Library
- H. Attiya and A. Fouren. 2001. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 2, 642--664. Google ScholarDigital Library
- H. Attiya, N. Lynch, and N. Shavit. 1994. Are wait-free algorithms fast? J. ACM 41, 4, 725--763. Google ScholarDigital Library
- H. Attiya and O. Rachman. 1998. Atomic Snapshots in O(n log n) Operations. SIAM J. Comput. 27, 2, 319--340. Google ScholarDigital Library
- E. Borowsky and E. Gafni. 1993. Immediate atomic snapshots and fast renaming. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing. 41--51. Google ScholarDigital Library
- F. E. Fich. 2005. How hard is it to take a snapshot? In Proceedings of 31st Annual Conference on Current Trends in Theory and Practice of Informatics (SOFSEM). Lecture Notes in Computer Science, vol. 3381, Springer, 27--35. Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Prog. Lang. Syst. 12, 3, 463--492. Google ScholarDigital Library
- M. Inoue, T. Masuzawa, W. Chen, and N. Tokura. 1994. Linear-Time Snapshot Using Multi-writer Multi-reader Registers. In Proceedings of the 8th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science, vol. 857, Springer, 130--140. Google ScholarDigital Library
- P. Jayanti. 2002. f-arrays: Implementation and applications. In Proceedings of the 21st Annual Symposium on Principles of Distributed Computing (PODC). ACM, New York, 270--279. Google ScholarDigital Library
- P. Jayanti. 2005. An optimal multi-writer snapshot algorithm. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). 723--732. Google ScholarDigital Library
- P. Jayanti and S. Petrovic. 2005. Efficient wait-free implementation of multiword LL/SC variables. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, 59--68. Google ScholarDigital Library
- P. Jayanti, K. Tan, and S. Toueg. 2000. Time and space lower bounds for nonblocking implementations. SIAM J. Comput. 30, 2, 438--456. Google ScholarDigital Library
- Y. Riany, N. Shavit, and D. Touitou. 2001. Towards a practical snapshot algorithm. Theoret. Comput. Sci. 269, 1--2, 163--201.Google ScholarCross Ref
Index Terms
- Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity
Recommendations
Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed ComputingWe present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads ...
Faster than optimal snapshots (for a while): preliminary version
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computingThis paper presents a novel implementation of a snapshot object for n processes, with O(log2blogn) step complexity for update operations and O(logb) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and ...
Comments