The computability of relaxed data structures: queues and stacks as examples |
| |
Authors: | Nir Shavit Gadi Taubenfeld |
| |
Affiliation: | 1.MIT,Cambridge,USA;2.Tel-Aviv University,Tel Aviv,Israel;3.The Interdisciplinary Center,Herzliya,Israel |
| |
Abstract: | Most concurrent data structures being designed today are versions of known sequential data structures. However, in various cases it makes sense to relax the semantics of traditional concurrent data structures in order to get simpler and possibly more efficient and scalable implementations. For example, when solving the classical producer-consumer problem by implementing a concurrent queue, it might be enough to allow the dequeue operation (by a consumer) to return and remove one of the two oldest values in the queue, and not necessarily the oldest one. We define infinitely many possible relaxations of several traditional data structures and objects: queues, stacks, multisets and registers, and examine their relative computational power. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|