A simple abstraction for complex concurrent indexes
A simple abstraction for complex concurrent indexes
复制标题
复杂并发索引的简单抽象
DOI：
10.1145/2048066.2048131
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Da Rocha Pinto P
中科院分区：
文献类型：
--
作者：
Da Rocha Pinto P
索引无处不在。例如，关联数组、字典、映射和散列在数据库、文件系统和动态语言等应用程序中使用。抽象地说，顺序索引可以看作是从键到值的部分函数。可以通过键来查询值，并且可以通过添加或删除映射来改变索引。虽然这个抽象规范非常简单，但它不足以解释并发访问的索引。提出了并发索引的抽象规范。我们使用我们的规范验证了几个有代表性的并发客户机应用程序，证明客户机可以进行抽象推理，而不必考虑特定的底层实现。但是，如果并发索引的标准实现不能满足我们的规范，那么我们的规范就没有任何意义。我们验证了基于链表、哈希表和B-Link树的算法是否满足我们的规范。这些算法的复杂性，特别是B-Link树算法，可以通过我们的抽象规范完全隐藏在客户端视图之外。
Indexes are ubiquitous. Examples include associative arrays, dictionaries, maps and hashes used in applications such as databases, file systems and dynamic languages. Abstractly, a sequential index can be viewed as a partial function from keys to values. Values can be queried by their keys, and the index can be mutated by adding or removing mappings. Whilst appealingly simple, this abstract specification is insufficient for reasoning about indexes accessed concurrently. We present an abstract specification for concurrent indexes. We verify several representative concurrent client applications using our specification, demonstrating that clients can reason abstractly without having to consider specific underlying implementations. Our specification would, however, mean nothing if it were not satisfied by standard implementations of concurrent indexes. We verify that our specification is satisfied by algorithms based on linked lists, hash tables and B-Link trees. The complexity of these algorithms, in particular the B-Link tree algorithm, can be completely hidden from the client's view by our abstract specification.
登录
查看更多内容
IEEE Transactions on Software Engineering 1 数据结构一致性的模块化可插入分析
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Viktor Kunčak;Patrick Lam;Karen Zee;M. Rinard
通讯作者：
M. Rinard
关于并发索引的推理
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Pedro da Rocha Pinto
通讯作者：
Pedro da Rocha Pinto
影响因子：
1.1
作者：
Filipovic I
通讯作者：
Filipovic I
NOSQL 中的缓存和一致性
DOI：
--
发表时间：
2010
期刊：
International Conference on Computer Science and Information Technologies
影响因子：
--
作者：
Peng Xiang;Ruichun Hou;Zhi
通讯作者：
Zhi
带超车的 B 树并发操作
DOI：
--
发表时间：
1985
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
Y. Sagiv
通讯作者：
Y. Sagiv