ICPPManish.pdf (332 kB)

A Relaxed Balanced Non-Blocking Binary Search Tree

Download (332 kB)
conference contribution
posted on 10.11.2020, 01:37 by Manish Singh, lindsay Groves, Alex Potanin
We present a new relaxed balanced concurrent binary search tree in which all operations are non-blocking. We utilise the notion of separating balancing operation and update operations in a concurrent environment and design a nonblocking balancing operation in addition to the regular insert, search, and relaxed delete operations. Our design uses a single-word CAS supported by most modern CPUs.

History

Preferred citation

Singh, M., Groves, L. & Potanin, A. (n.d.). A Relaxed Balanced Non-Blocking Binary Search Tree. In 48th International Conference on Parallel Processing August 5-8, 2019, Kyoto Research Park, Kyoto, Japan, Kyoto, Japan.

Conference name

48th International Conference on Parallel Processing August 5-8, 2019, Kyoto Research Park, Kyoto, Japan

Conference Place

Kyoto, Japan

Conference start date

05/08/2019

Conference finish date

08/08/2019

Contribution type

Poster; Abstract

Publication status

Published online

Exports

Logo branding

Categories

Exports