M.Sc Student | Erez Michalak |
---|---|

Subject | An Adaptive Technique for Constructing Robust and High-Throughput Shared Objects |

Department | Department of Industrial Engineering and Management |

Supervisors | Full Professor Kutten Shay |

Dr. Danny Hendler | |

Full Thesis text |

Shared counters are the key to solving a variety of coordination problems on multiprocessor machines, such as barrier synchronization and index distribution. It is desired that they, like shared objects in general, be robust, linearizable and scalable. We present the first linearizable and wait-free shared counter algorithm that achieves high throughput without any a-priori knowledge of the execution. In particular, in an

*N*-process execution *E*, our algorithm achieves high
throughput of *Omega(N/((K _{E }logK_{E})^{2}logN))*,
where

Our algorithm is an adaptive version of a prior art linearizable and
lock-free algorithm. The original non-adaptive version guarantees high
throughput only when some fixed *K *was given to the algorithm in advance
as a (supposed) upper bound of *K _{E}*. If the given

Our algorithm can be easily adapted for obtaining linearizable, wait-free and high throughput implementation of any shared object that supports a combinable operation (such as queues and stacks).

In order to ensure high throughput and wait-freedom, we needed a method that guarantees (for some common kind of concurrent procedures) the completion of a procedure in a finite and bounded time, regardless of the contention on the shared memory. This method may prove useful by itself, for solving other problems.