The complexity of updating snapshot objects. (English) Zbl 1231.68064
Summary: This paper proves \(\Omega (m)\) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an \(m\)-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of \(m\)-component single-writer snapshot objects from single-writer registers.
MSC:
| 68M14 | Distributed systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W15 | Distributed algorithms |
References:
| [1] | Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir: Atomic snapshots of shared memory, Journal of the ACM 40, No. 4, 873-890 (1993) · Zbl 0783.68029 · doi:10.1145/153724.153741 |
| [2] | Anderson, James H.: Composite registers, Distributed computing 6, No. 3, 141-154 (1993) · Zbl 0781.68042 · doi:10.1007/BF02242703 |
| [3] | Anderson, James H.: Multi-writer composite registers, Distributed computing 7, No. 4, 175-195 (1994) |
| [4] | James H. Aspnes, Maurice Herlihy, Wait-free data structures in the asynchronous PRAM model, in: Proceedings of the 2nd ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 340–349. |
| [5] | Attiya, Hagit; Fouren, Arie: Adaptive and efficient algorithms for lattice agreement and renaming, SIAM journal on computing 31, No. 2, 642-664 (2001) · Zbl 0994.68044 · doi:10.1137/S0097539700366000 |
| [6] | Attiya, Hagit; Herlihy, Maurice; Rachman, Ophir: Atomic snapshots using lattice agreement, Distributed computing 8, No. 3, 121-132 (1995) |
| [7] | Hagit Attiya, Eshcar Hillel, Alessia Milani, Inherent limitations on disjoint-access parallel implementations of transactional memory, in: Proceedings of the 21st ACM Symposium on Parallel Algorithms and Architectures, July 2009, pp. 69–78. · Zbl 1253.68025 |
| [8] | Attiya, Hagit; Rachman, Ophir: Atomic snapshots in \(O(nlogn)\) operations, SIAM journal on computing 27, No. 2, 319-340 (1998) · Zbl 0907.68053 · doi:10.1137/S0097539795279463 |
| [9] | Attiya, Hagit; Welch, Jennifer: Distributed computing: fundamentals, simulations and advanced topics, (2004) · Zbl 0910.68077 |
| [10] | Dwork, Cynthia; Herlihy, Maurice; Plotkin, Serge; Waarts, Orli: Time-lapse snapshots, SIAM journal on computing 28, No. 5, 1848-1874 (1999) · Zbl 0928.68135 · doi:10.1137/S0097539793243685 |
| [11] | Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, in: Proceedings of the 35th ACM Symposium on Theory of Computing, June 2003, pp. 259–268. · Zbl 1192.68082 · doi:10.1145/780542.780582 |
| [12] | Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert, Time-space tradeoffs for implementations of snapshots, in: Proceedings of the 38th ACM Symposium on Theory of Computing, May 2006, pp. 169–178. · Zbl 1301.68187 |
| [13] | Fatourou, Panagiota; Fich, Faith Ellen; Ruppert, Eric: Time lower bounds for implementations of multi-writer snapshots, Journal of the ACM 54, No. 6 (2007) · Zbl 1312.68022 |
| [14] | Panagiota Fatourou, Nikolaos D. Kallimanis, Single-scanner multi-writer snapshot implementations are fast, in: Proceedings of the 25st Annual ACM Symposium on Principles of Distributed Computing, July 2006, pp. 228–237. · Zbl 1314.68373 |
| [15] | Panagiota Fatourou, Nikolaos D. Kallimanis, Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS, in: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, August 2007, pp. 33–42. · Zbl 1283.68242 |
| [16] | Fich, Faith Ellen: How hard is it to take a snapshot?, Lecture notes in computer science 3381, 27-35 (2005) · Zbl 1117.68320 |
| [17] | Fich, Faith; Herlihy, Maurice; Shavit, Nir: On the space complexity of randomized synchronization, Journal of the ACM 45, No. 5, 843-862 (1998) · Zbl 1065.68543 · doi:10.1145/290179.290183 |
| [18] | Fich, Faith Ellen; Ruppert, Eric: Hundreds of impossibility results for distributed computing, Distributed computing 16, No. 2–3, 121-163 (2003) |
| [19] | Herlihy, Maurice: Wait-free synchronization, ACM transactions on programming languages and systems 13, No. 1, 124-149 (1991) · Zbl 1314.68380 |
| [20] | Herlihy, Maurice P.; Wing, Jeannette M.: Linearizability: a correctness condition for concurrent objects, ACM transactions on programming languages and systems 12, No. 3, 463-492 (1990) |
| [21] | Inoue, Michiko; Chen, Wei; Masuzawa, Toshimitsu; Tokura, Nobuki: Linear time snapshots using multi-writer multi-reader registers, Lncs 857, 130-140 (1994) |
| [22] | Israeli, A.; Shaham, A.; Shirazi, A.: Linear-time snapshot implementations in unbalanced systems, Mathematical systems theory 28, No. 5, 469-486 (1995) · Zbl 0833.68047 · doi:10.1007/BF01185868 |
| [23] | Israeli, Amos; Shirazi, Assaf: The time complexity of updating snapshot memories, Information processing letters 65, No. 1, 33-40 (1998) · Zbl 1339.68022 |
| [24] | Prasad Jayanti, f-arrays: implementation and applications, in: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, July 2002, pp. 270–279. · Zbl 1292.68028 |
| [25] | Prasad Jayanti, An optimal multi-writer snapshot algorithm, in: Proceedings of the 37th ACM Symposium on Theory of Computing, May 2005, pp. 723–732. · Zbl 1192.68449 · doi:10.1145/1060590.1060697 |
| [26] | Jayanti, Prasad; Tan, King; Toueg, Sam: Time and space lower bounds for nonblocking implementations, SIAM journal on computing 30, No. 2, 438-456 (2000) · Zbl 0968.68064 · doi:10.1137/S0097539797317299 |
| [27] | Kirousis, L. M.; Spirakis, P.; Tsigas, P.: Reading many variables in one atomic operation: solutions with linear or sublinear complexity, IEEE transactions on parallel and distributed systems 5, No. 7, 688-696 (1994) |
| [28] | Lynch, Nancy: Distributed algorithms, (1996) · Zbl 0877.68061 |
| [29] | Riany, Yaron; Shavit, Nir; Touitou, Dan: Towards a practical snapshot algorithm, Theoretical computer science 269, No. 1–2, 163-201 (2001) · Zbl 0983.68240 · doi:10.1016/S0304-3975(00)00412-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
