Time-space tradeoffs for implementations of snapshots

ABSTRACT

A snapshot object is an abstraction of the fundamental problem of obtaining a consistent view of the contents of the shared memory in a distributed system while other processes may concurrently update those contents. A snapshot object stores an array of m components and can be accessed by two operations: an UPDATE that changes the value of an individual component and a powerful SCAN that returns the contents of the entire array.This paper proves time-space tradeoffs for fault-tolerant implementations of a snapshot object from registers that support only Read and Write operations. For anonymous implementations (where all processes are programmed identically), we prove that a SCAN requires Ω(n/r) time, where n is the number of processes in the system and r is the number of registers used by the implementation. For the general non-anonymous case, we prove that, for any fixed r, the time required to do a SCAN grows without bound as n increases. These tradeoffs hold even in the case where the snapshot object has just two components.This is the first time a lower bound on the tradeoff between time complexity and the number of registers has been proved for any problem in asynchronous shared-memory systems. We introduce a new tool for proving distributed lower bounds: the notion of a shrinkable execution, from which an adversary can remove portions as necessary.

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 , Gideon Stupp, Optimal time-space tradeoff for shared memory leader election, Journal of Algorithms, v.25 n.1, p.95-117, Oct. 1997 [doi>10.1006/jagm.1996.0852]
• 3: Rajeev Alur , Gadi Taubenfeld, Contention-free complexity of shared memory algorithms, Information and Computation, v.126 n.1, p.62-73, April 10, 1996 [doi>10.1006/inco.1996.0034]
• 4: James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993 [doi>10.1007/BF02242703]
• 5: James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994 [doi>10.1007/BF02280833]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Hagit Attiya, Panagiota Fatourou, and Faith Ellen Fich. A lower bound on update time for multi-writer snapshot objects. Manuscript, 2004.
• 10: 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]
• 11: 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]
• 12: Hagit Attiya , Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
• 13: Oliver Berthold , Hannes Federrath , Marit Köhntopp, Project “anonymity and unobservability in the Internet”, Proceedings of the tenth conference on Computers, freedom and privacy: challenging the assumptions, p.57-65, April 04-07, 2000, Toronto, Ontario, Canada [doi>10.1145/332186.332211]
• 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: Panagiota Fatourou , Faith Fich , Eric Ruppert, Space-optimal multi-writer snapshot objects are slow, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571828]
• 16: Panagiota Fatourou , Faith Fich , Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780582]
• 17: 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]
• 18: Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003 [doi>10.1007/s00446-003-0091-y]
• 19: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 20: Rainer Gawlick , Nancy A. Lynch , Nir Shavit, Concurrent Timestamping Made Simple, Proceedings of the Israel Symposium on Theory of Computing and Systems, p.171-183, May 01, 1992
• 21: Rachid Guerraoui and Eric Ruppert. What can be implemented anonymously? In Proc. 19th International Symposium on Distributed Computing, volume 3724 of LNCS, pages 244--259, 2005.
• 22: Danny Hendler , Nir Shavit, Operation-valency and the cost of coordination, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.84-91, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872047]
• 23: 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]
• 24: 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
• 25: 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]
• 26: 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]
• 27: George Lucas and Jonathan Hales. Star Wars: Episode II--Attack of the Clones {motion picture}. Twentieth Century Fox, 2002.
• 28: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 29: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 30: E. Schenk, Faster approximate agreement with multi-writer registers, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.714, October 23-25, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

General Terms:
Theory

Keywords:
anonymous processes, distributed computing, lower bound, shared memory, snapshot, time-space tradeoff, wait-free