You are here

UCF Digital Collections ยป ETD Collection

A Comparison of Concurrent Correctness Criteria for Shared Memory Based Data Structure

Download pdf | Full Screen View

Date Issued:
2016
Abstract/Description:
Developing concurrent algorithms requires safety and liveness to be defined in order to understand their proper behavior. Safety refers to the correctness criteria while liveness is the progress guarantee. Nowadays there are a variety of correctness conditions for concurrent objects. The way these correctness conditions differ and the various trade-offs they present with respect to performance, usability, and progress guarantees is poorly understood. This presents a daunting task for the developers and users of such concurrent algorithms who are trying to better understand the correctness of their code and the various trade-offs associated with their design choices and use. The purpose of this study is to explore the set of known correctness conditions for concurrent objects, find their correlations and categorize them, and provide insights regarding their implications with respect to performance and usability. In this thesis, a comparative study of Linearizability, Sequential Consistency, Quiescent Consistency and Quasi Linearizability will be presented using data structures like FIFO Queues, Stacks, and Priority Queues, and with a case study for performance of these implementations using different correctness criteria.
Title: A Comparison of Concurrent Correctness Criteria for Shared Memory Based Data Structure.
31 views
10 downloads
Name(s): Bhattacharya, Dipanjan, Author
Dechev, Damian, Committee Chair
Leavens, Gary, Committee Member
Bassiouni, Mostafa, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2016
Publisher: University of Central Florida
Language(s): English
Abstract/Description: Developing concurrent algorithms requires safety and liveness to be defined in order to understand their proper behavior. Safety refers to the correctness criteria while liveness is the progress guarantee. Nowadays there are a variety of correctness conditions for concurrent objects. The way these correctness conditions differ and the various trade-offs they present with respect to performance, usability, and progress guarantees is poorly understood. This presents a daunting task for the developers and users of such concurrent algorithms who are trying to better understand the correctness of their code and the various trade-offs associated with their design choices and use. The purpose of this study is to explore the set of known correctness conditions for concurrent objects, find their correlations and categorize them, and provide insights regarding their implications with respect to performance and usability. In this thesis, a comparative study of Linearizability, Sequential Consistency, Quiescent Consistency and Quasi Linearizability will be presented using data structures like FIFO Queues, Stacks, and Priority Queues, and with a case study for performance of these implementations using different correctness criteria.
Identifier: CFE0006263 (IID), ucf:51046 (fedora)
Note(s): 2016-08-01
M.S.
Engineering and Computer Science, Computer Science
Masters
This record was generated from author submitted information.
Subject(s): Concurrency -- Correctness Criteria -- Data Structures -- Performance -- Complexity of Design
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0006263
Restrictions on Access: campus 2017-08-15
Host Institution: UCF

In Collections