2020/03/16 by Thomas Dickerson, Dickerson, Thomas · 1 voice
Computer Science · #Advanced Data Storage Technologies #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.PL
paper · pdf · doi:10.48550/arxiv.2003.07395
openalex publication_date 2020/03/16 · arxiv published 2020/03/16 · arxiv updated 2020/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work unifies insights from the systems and functional programming communities, in order to enable compositional reasoning about software which is nonetheless efficiently realizable in hardware. It exploits a correspondence between design goals for efficient concurrent data structures and efficient immutable persistent data structures, to produce novel implementations of mutable concurrent trees with low contention and an efficient snapshot operation to support speculative execution models. It also exploits commutativity to characterize a design space for integrating traditional high-performance concurrent data structures into Software Transactional Memory (STM) runtimes, and extends this technique to yield a novel algorithm for concurrent execution of so-called ``smart contracts'' (specialized programs which manipulate the state of blockchain ledgers).