Reasoning about Concurrent Indexes
Reasoning about Concurrent Indexes
复制标题
关于并发索引的推理
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Pedro da Rocha Pinto
中科院分区：
文献类型：
--
作者：
Pedro da Rocha Pinto
索引数据结构（如B+树和哈希表）被广泛用作数据库和文件系统的核心。在一个并发系统像服务器一样普遍，并且像个人计算机一样大量增加的世界里，我们需要一种方法来确保并发实现不包含错误。我们使用多个实现共享公共高级规范的事实，并使用并发抽象谓词来证明实现满足这样的规范。这种方法允许我们重用抽象规范，并支持独立于低级实现的高级推理。
Index data structures such as B+ trees and hash tables are used widely as the core of databases and file systems. In a world where concurrent systems are common as servers and largely increasing as personal computers, we need a way to make sure concurrent implementations do not contain bugs. We use the fact that multiple implementations share a common high-level specification and use concurrent abstract predicates to prove that an implementation satisfies such a specification. This approach allows us to reuse the abstract specification and enables high-level reasoning independent from the low-level implementation.