טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMichalak Erez
SubjectAn Adaptive Technique for Constructing Robust and
High-Throughput Shared Objects
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Shay Kutten
Dr. Danny Hendler
Full Thesis textFull thesis text - English Version


Abstract

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/((KE logKE)2logN)), where KE is E's unknown level of asynchrony. Our algorithm adapts dynamically to the unknown KE, but only up to some threshold. Over this threshold, our algorithm shifts to an asynchronous mode of operation, in which better throughput is achieved for that high level of asynchrony. Moreover, let K'E be a fixed upper bound on the relative speeds of different processes, at a time that both of them participated in E and none of them failed. Then, we can generalize the guarantee of our algorithm (for any constant number of failures) to the high throughput of Omega(N/((K'E logK'E)2logN)).

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 KE. If the given K happened to be lower than KE, or much greater than KE, then the throughput of that algorithm degraded significantly. In addition, our algorithm is more robust, as it satisfies the wait-freedom progress guarantee, while the non-adaptive version is only lock-free.

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.