M.Sc Thesis | |

M.Sc Student | Kaplan Yaniv |
---|---|

Subject | Lower Bounds for Adaptive Collect and Related Objects |

Department | Department of Computer Science |

Supervisor | PROF. Hagit Attiya |

*Adaptive* algorithms, whose step complexity adjusts to the
number of active processes, are attractive for situations in which the number
of participating processes is highly variable. This thesis studies the number
and type of multi-writer registers that are needed for adaptive algorithms.

We prove that if a
collect algorithm is *f*-adaptive to total contention, namely, its step
complexity is *f(k)*, where *k* is the number of processes that ever
took a step, then it uses Ω(*f ^{-1}(n)*) multi-writer
registers, where

Furthermore, we show
that competition for the underlying registers is inherent for adaptive collect
algorithms. We consider *c-write* registers, to which at most *c* processes
can be concurrently about to write. Special attention is given to *concurrent-write*
registers, the case *c=n* where any amount of competition is allowed, and *exclusive-write*
registers, the case *c=*1 where no competition is allowed.

A collect algorithm that
is *f*-adaptive to point contention, namely, its step complexity is *f(k)*,
where k is the maximum number of simultaneously active processes, is shown to
require Ω (*f ^{-1}(n/c)*) concurrent-write registers, even if
an unlimited number of

Finally, we present
lower bounds on the step complexity in solo executions (i.e., without any
contention), when only *c*-write registers are used: for weak test&set
objects we present an Ω (*(log n)/(log c + loglog n)*) lower bound,
while for collect and sensitive objects the lower bound is Ω (*(n-1)/c*).