Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract)

ABSTRACT

In this paper we prove: For any constant d there is a large enough n such that there is no long-lived adaptive implementation of collect or renaming in the read write model with n processes that uses d or less MWMR registers. In other words, there is no implementation of a long-lived and adaptive renaming or collect object in the atomic read/write model that uses O(1) multi-writer-multi-reader registers and any number of single-writer-multi-reader registers. In 1980 Burns and Lynch [1] proved that at least n multi-writer-multi-reader (MWMR) registers are necessary in any mutual exclusion algorithm that uses only MWMR registers (i.e., atomic registers). It is also relatively easy to see that any adaptive non-trivial algorithm uses at least one multi-writer-multi-reader (MWMR) register even when there are n single-writer-multi-reader (SWMR) registers. Here we extend the techniques of Burns and Lynch and prove that adaptive algorithms that use both SWMR and MWMR registers such as, collect and renaming, need in addition to the &OHgr;(n) SWMR registers a non-constant, F(n) number of MWMR registers.

REFERENCES

• 1: 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 ]
• 2: H. Attiya and A. Fouren. Adaptive long-lived renaming with read and write operations. Technical Report 0956, Faculty of Computer Science, Technion, Haifa, 1999. http://www, cs. t echnion, ac. il/,~ h agit/pubs/ tr0956.ps.gz.
• 3: Yehuda Afek , Gideon Stupp , Dan Touitou, Long-Lived Adaptive Collect with Applications, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.262, October 17-18, 1999
• 4: Y. Afek, H. Attiya, G. Stupp, and D. Touitou. Adaptive long-lived renaming using bounded memory. Submitted to DISC99. ftp://ftp.math.tau.ac.il/pub/stupp/PAPERS/ name99.ps.gz, 1999.
• 5: 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 ]
• 6: Y. Afek, E. Gafni, and M. Merritt. Adaptive algorithms utilyzing adaptive collect and snapshot. Submitted for publication, ftp://ftp.math.tau.ac.il/pub/afek/lshotRn.ps, 1999.
• 7: Y. Afek, P. Boxer, and D. Touitou. Bounds on the shared memory requirements for long-lived & adaptive objects. Draft of full paper, ftp://ftp.math.tau.ac.il/ pub/afek/abt.ps.
• 8: H. Attiya and A. Fouren. Adaptive long-lived renaming with read and write operations. Extended Abstract, November 1998.
• 9: Yehuda Afek , Hagit Attiya , Arie Fouren , Gideon Stupp , Dan Touitou, Long-lived renaming made adaptive, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.91-103, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301335]
• 10: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 11: Mark Moir , James H. Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, v.25 n.1, p.1-39, Oct. 1995 [doi>10.1016/0167-6423(95)00009-H ]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Theory, Verification