E-Locus - Institutional Repository of the University of Crete

Home Search

Results - Details

Search command : Author="Κιοστεράκης" And Author="Χαρίδημος" And Author="Μ."

Current Record: 1 of 1

[Add to Basket]

Identifier

000429246

Title

Efficient implementations of concurrent snapshot objects

Alternative Title

Αποδοτικές υλοποιήσεις ατομικών στιγμιοτύπων κοινόχρηστης μνήμης

Author

Κιοστεράκης, Χαρίδημος Μ.

Thesis advisor

Κατεβαίνης, Μανώλης
Καλλιμάνης, Νικόλαος

Reviewer

Μαρκάτος, Ευάγγελος
Μαγκούτης, Κωνσταντίνος

Abstract

During the last decade, there was a rise on the use of multicore and many-core systems. Their application covers a huge range, from customer products like smartphones and laptops to servers that equip modern data centers. The multicore and many-core systems can provide better performance only if the user can use their potential, although this is not a trivial task since parallel programming is much harder than serial programming. In order to use to the fullest the power of such a system, utilization of efficient implementations of concurrent data structures is needed. A snapshot object is a concurrent data structure that has numerous applications in concurrent programming. Snapshots can be used to record the state of the system, so they can provide solutions to problems where an action should be taken when the global state of the system satisfies some conditions. Furthermore, snapshots have been widely used for the design and verification of distributed algorithms such as the construction of concurrent timestamps and randomized consensus. A snapshot object is a concurrent data structure that consists of 𝑚 components, each component storing a value from a given set. Processes can read/modify the state of the object by executing the operations 𝑈𝑃𝐷𝐴𝑇𝐸 and 𝑆𝐶𝐴𝑁. An 𝑈𝑃𝐷𝐴𝑇𝐸 operation gives processes the ability to change the value of a component of the snapshot, while the 𝑆𝐶𝐴𝑁 operation returns a “consistent” view of all the components of the object. In this thesis, two variants of concurrent snapshot objects are studied. The first one is the singlescanner snapshot object which, can support only one active 𝑆𝐶𝐴𝑁 operation on any given time (whilst supporting many concurrent 𝑈𝑃𝐷𝐴𝑇𝐸 operations). The second one is the multi-scanner snapshot object that can support multi concurrent 𝑆𝐶𝐴𝑁 operations at any given time. A variation of a multi-scanner snapshot object is a λ-scanner snapshot object, where the latter can support only λ different 𝑆𝐶𝐴𝑁 operations to be active at any given time. In this work, two wait-free, linearizable implementations of snapshot objects are presented. The first one is an implementation of a single-scanner snapshot object, and the second one is an implementation of a λ-scanner snapshot object. The operations that are supported by those implementations have a step complexity that doesn’t correlate with the number of active processes of the system 𝑛, while the space and step complexity of the λ-scanner object is a function of λ. Furthermore, our implementations have been designed to maintain relatively low space complexity even if that means sacrificing some step complexity. The low space complexity that our implementations provide makes them more appealing in real system applications. We first povide a simple implementation of a single-scanner snapshot object, called 1 − 𝑂𝑃𝑇. This implementation uses 𝑂(𝑚) 𝐶𝐴𝑆 registers of unbounded size. The 𝑈𝑃𝐷𝐴𝑇𝐸 has a step complexity of 𝑂(1), while the 𝑆𝐶𝐴𝑁 has a step complexity of 𝑂(𝑚). Then we present a λ-scanner snapshot object, called 𝜆 − 𝑂𝑃𝑇 that is based on 1 − 𝑂𝑃𝑇. When the number of λ is equal to the number of processes in the system, 𝜆 − 𝑂𝑃𝑇 implements a multi-scanner object. This implementation uses 𝑂(𝜆𝑚) 𝐶𝐴𝑆 registers of unbounded size. The 𝑈𝑃𝐷𝐴𝑇𝐸 implementation has a step complexity of 𝑂(𝜆), and the 𝑆𝐶𝐴𝑁 has a step complexity of 𝑂(𝜆𝑚). This implementation is also wait-free and provides a trade-off between the step/space complexity and the maximum number of 𝑆𝐶𝐴𝑁 operations that can afford to be active on any given point in time.

Language

English

Subject

Concurrent algorithms

Concurrent data structures

Κατανεμημένες δομές δεδομένων

Κατανεμημένος αλγόριθμος

Στιγμιότυπα

Issue date

2020-03-27

Collection

School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses