<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
A mechanized refinement proof of the Chase-Lev deque using a proof system

Loading...
Thumbnail Image

Departments

School / College / Institute

Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Taşıran, Serdar

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

We present a linearizability proof for the concurrent Chase-Lev work-stealing queue (WSQ) implementation on sequentially consistent memory. We used the CIVL proof system to carry out the proof. The lowest-level description of the WSQ is the data structure code described in terms of fine-grained actions whose atomicity is guaranteed by hardware. Higher level descriptions consist of increasingly coarser action blocks obtained using a combination of Owicki-Gries (OG) annotations and reduction and abstraction. We believe that the OG annotations (location invariants) we provided to carry out the refinement proofs at each level provide insight into the correctness of the algorithm. The top-level description for the WSQ consists of a single atomic action for each data structure operation, where the specification of the action is tight enough to show that the WSQ data structure is linearizable.

Source

Publisher

Springer

Citation

item.page.haspartof

Source

Computing

item.page.ispartofseries

item.page.edition

DOI

10.1007/s00607-018-0635-4

item.page.datauri

item.page.link

Rights

N/A

Copyrights Note

Rights and licensing

N/A

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Item type:Goal, Access status: Open Access ,
04 - Quality Education
Education liberates the intellect, unlocks the imagination and is fundamental for self-respect. It is the key to prosperity and opens a world of opportunities, making it possible for each of us to contribute to a progressive, healthy society. Learning benefits every human being and should be available to all.
Item type:Goal, Access status: Open Access ,
05 - Gender Equality
Gender bias is undermining our social fabric and devalues all of us. It is not just a human rights issue; it is a tremendous waste of the world’s human potential. By denying women equal rights, we deny half the population a chance to live life at its fullest. Political, economic and social equality for women will benefit all the world’s citizens. Together we can eradicate prejudice and work for equal rights and respect for all.
Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators