The Taub Faculty of Computer Science Events and Talks

The rapid deployment of multi-core architectures has resulted in a dire need for scalable and reliable concurrent algorithms. This dissertation focuses on the design of concurrent data structures, which constitute building blocks for concurrent algorithms. Two major design goals in this domain are reliability and efficiency. This talk will concentrate on the hardness of reclaiming concurrent data-structures' memory efficiently, while taking care to preserve reliability. It will include (1) the design of a novel and efficient concurrent reclamation scheme, (2) its application to multi version concurrency control (i.e., range queries), and (3) a general impossibility demonstrating the hardness of designing reliable memory reclamation schemes.