Your browser does not support JavaScript!

Home    Collections    Type of Work    Post-graduate theses  

Post-graduate theses

Current Record: 8 of 4817

Back to Results Previous page
Next page
Add to Basket
[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   Faculty/Department--Faculty of Sciences and Engineering--Department of Computer Science--Post-graduate theses
  Type of Work--Post-graduate theses
Permanent Link Bookmark and Share
Views 589

Digital Documents
No preview available

No permission to view document.
It won't be available until: 2021-03-27