Bounds on the shared memory requirements for Long-Lived \& Adaptive objects

Yehuda Afek Pazi Boxer Dan Touitou

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


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 no more than d MWMR register. 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. In 1989 Burns and Lynch [bl93] proved that at least n single-writer-multi-reader (SWMR) registers are necessary in any mutual exclusion algorithm. It is relatively easy to see that any adaptive non-trivial algorithm uses at least one multi-writer-multi-reader (MWMR) register. Here we extend the techniques of Burns and Lynch and prove that adaptive algorithms such as, collect and renaming, need in addition to the Omega(n) SWMR registers a non-constant, F(n) number of MWMR registers.