@inbook{bceedab026a148178f44f57e684beb5a,
title = "Automated Verification of Concurrent Search Structures",
abstract = "Search structures support the fundamental data storage primitives on key-value pairs: insert a pair, delete by key, search by key, and update the value associated with a key. Concurrent search structures are parallel algorithms to speed access to search structures on multicore and distributed servers. These sophisticated algorithms perform fine-grained synchronization between threads, making them notoriously difficult to design correctly. Indeed, bugs have been found both in actual implementations and in the designs proposed by experts in peer-reviewed publications. The rapid development and deployment of these concurrent algorithms has resulted in a rift between the algorithms that can be verified by the state-of-The-Art techniques and those being developed and used today. The goal of this book is to show how to bridge this gap in order to bring the certified safety of formal verification to high-performance concurrent search structures. Similar techniques and frameworks can be applied to concurrent graph and network algorithms beyond search structures.",
keywords = "B trees, concurrency, data structures, hash structures, log-structured merge trees, search structures, separation logic, verification",
author = "Siddharth Krishna and Nisarg Patel and Dennis Shasha and Thomas Wies",
note = "Funding Information: We would like to acknowledge the very careful external reviews by Maurice Herlihy, Eddie Kohler, Robbert Krebbers, K. Rustan M. Leino, and Peter M{\"u}ller. In addition, we warmly acknowledge Elizabeth Dietrich and Rafael Sofaer for their careful reading during the preparation of this manuscript. We are also thankful to Alexander Summers for his contributions to the development of the flow framework, which is one of the pillars of our verification technique. Because our work was built largely on Iris, we would like to acknowledge the support received from the Iris Helpdesk, especially from Ralf Jung and Robbert Krebbers. Much of this work has been funded by the National Science Foundation under grants CCF-1618059, CCF-1815633, MCB-0929339, and NYU Wireless. The first author is grateful for the support of Microsoft Research Cambridge and his research team. Our publisher, Diane Cerra of Morgan & Clay-pool, has been very understanding with our obsessive natures. In addition to Diane, we would like to thank Christine Kiilerich, C.L. Tondo, and Brent and Sue Beckley. Publisher Copyright: Copyright {\textcopyright} 2021 by Morgan Claypool.",
year = "2020",
month = jun,
day = "1",
doi = "10.2200/S01089ED1V01Y202104CSL013",
language = "English (US)",
series = "Synthesis Lectures on Computer Science",
publisher = "Morgan and Claypool Publishers",
number = "1",
pages = "1--188",
booktitle = "Synthesis Lectures on Computer Science",
address = "United States",
edition = "1",
}