Space-optimal multi-writer snapshot objects are slow

ABSTRACT

We consider the problem of wait-free implementation of a multi-writer snapshot object with m ≥ 2 components shared by n > m processes. It is known that this can be done using m multi-writer registers. We give a matching lower bound, slightly improving the previous space lower bound. The main focus of the paper, however, is on time complexity. The best known upper bound on the number of steps a process has to take to perform one operation of the snapshot is O(n). When m is much smaller than n, an implementation whose time complexity is a function of m rather than n would be better. We show that this cannot be achieved for any space-optimal implementation: We prove that Ω(n) steps are required to perform a SCAN operation in the worst case, even if m = 2. This significantly improves previous Ω(min(m, n)) lower bounds. Our proof also yields insight into the structure of any space-optimal implementation, showing that processes simulating the snapshot operations must access the registers in a very constrained way.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 2: Yehuda Afek , Pazi Boxer , Dan Touitou, Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.81-89, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343523]
• 3: James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993 [doi>10.1007/BF02242703]
• 4: James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994 [doi>10.1007/BF02280833]
• 5: James H. Anderson , Yong-Jik Kim, An improved lower bound for the time complexity of mutual exclusion, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.90-99, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383996]
• 6: James H. Anderson , Jae-Heon Yang, Time/contention trade-offs for multiprocessor synchronization, Information and Computation, v.124 n.1, p.68-84, Jan. 10, 1996 [doi>10.1006/inco.1996.0006]
• 7: James Aspnes, Time- and space-efficient randomized consensus, Journal of Algorithms, v.14 n.3, p.414-431, May 1993 [doi>10.1006/jagm.1993.1022]
• 8: James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
• 9: J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
• 10: Hagit Attiya , Alla Gorbach , Shlomo Moran, Computing in Totally Anonymous Asynchronous Shared Memory Systems, Proceedings of the 12th International Symposium on Distributed Computing, p.49-61, September 24-26, 1998
• 11: Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994 [doi>10.1145/179812.179902]
• 12: Hagit Attiya , Ophir Rachman, Atomic Snapshots in O (n log n) Operations, SIAM Journal on Computing, v.27 n.2, p.319-340, April 1998 [doi>10.1137/S0097539795279463]
• 13: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 14: James E. Burns , Nancy A. Lynch, Bounds on shared memory for mutual exclusion, Information and Computation, v.107 n.2, p.171-184, Dec. 1993 [doi>10.1006/inco.1993.1065]
• 15: Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Journal of the ACM (JACM), v.45 n.5, p.843-862, Sept. 1998 [doi>10.1145/290179.290183]
• 16: Rainer Gawlick , Nancy Lynch , Nir Shavit, Concurrent timestamping made simple, Symposium proceedings on Theory of computing and systems, p.171-183, June 1992, Haifa, Israel
• 17: Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112602]
• 18: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 19: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 20: Michiko Inoue , Wei Chen, Linear-Time Snapshot Using Multi-writer Multi-reader Registers, Proceedings of the 8th International Workshop on Distributed Algorithms, p.130-140, September 29-October 01, 1994
• 21: A. Israeli, A. Shaham, and A. Shirazi. Linear-time snapshot implementations in unbalanced systems. Mathematical Systems Theory, 28(5), pages 469-486, September/October 1995.
• 22: Amos Israeli , Asaf Shirazi, The time complexity of updating snapshot memories, Information Processing Letters, v.65 n.1, p.33-40, Jan 1, 1998 [doi>10.1016/S0020-0190(97)00189-0]
• 23: Prasad Jayanti , King Tan , Sam Toueg, Time and Space Lower Bounds for Nonblocking Implementations, SIAM Journal on Computing, v.30 n.2, p.438-456, 2000 [doi>10.1137/S0097539797317299]
• 24: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 25: Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Journal of Computer and System Sciences, v.53 n.1, p.61-78, Aug. 1996 [doi>10.1006/jcss.1996.0049]