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.