[DBWorld] New Book - Automated Verification of Concurrent Search Structures

We are pleased to announce the latest title in Morgan & Claypool’s series on Data Management.

Automated Verification of Concurrent Search Structures
Siddharth Krishna, Microsoft Research, Cambridge
Nisarg Patel, New York University
Dennis Shasha, New York University
Thomas Wies, New York University

Paperback ISBN: 9781636391281
eBook ISBN: 9781636391298
Hardcover ISBN: 9781636391304
June 2021 | 188 Pages

http://www.morganclaypoolpublishers.com/catalog_Orig/product_info.php?products_id=1638

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 ca!
 n be appl
 ied to concurrent graph and network algorithms beyond search structures.

Table of Contents: 
Acknowledgments / Introduction / Preliminaries / Separation Logic / Ghost State / The Keyset Resource Algebra / The Edgeset Framework for Single-Copy Structures / The Flow Framework / Verifying Single-Copy Concurrent Search Structures / Verifying Multicopy Structures / The Edgeset Framework for Multicopy Structures / Reasoning about Non-Static and Non-Local Linearization Points / Verifying the LSM DAG Template / Proof Mechanization and Automation / Related Work, Future Work, and Conclusion / Bibliography / Authors' Biographies

Series: Computer Science
https://www.morganclaypoolpublishers.com/catalog_Orig/index.php?cPath=22&sort=2a&series=14

_______________________________________________
Please do not post msgs that are not relevant to the database community at large.  Go to www.cs.wisc.edu/dbworld for guidelines and posting forms.
To unsubscribe, go to https://lists.cs.wisc.edu/mailman/listinfo/dbworld