- Persistent data structures
dirty field is set to dirty when the leaf is affected by some update operations (
Validate check all leaves stored in
snap. If any
dirty field is true, than
Validate returns false.
RangeQuery follows few steps,
- Use DFS to populate
snapwith all leaves that may contain a key in range.
Validateto check all the leaves stored in
Validatereturns false, than retry.
- Extract all keys in range from
|-||snapshots in BST||range query in k-ary search trees|
|Efficiency||low (iterate all nodes while checking)||high|
Just personal opinion, may contain errors.
In the paper,
Theorem 3. All operations are non-blocking.
After discussing this with Keren, both of us feel it should be a bug.
But actually it’s correct.
If the update operations are always exist (insertion and deletion are frequently invoked), than
RangeQuerycannot return. So the
RangeQueryis actually blocked by these update operations.
Answer from Brown:
However, your intuition about range queries blocking is not quite correct. What you are referring to is starvation. Starvation can happen in any algorithm that is not wait-free. In order to be non-blocking, the algorithm simply needs to guarantee that, if operations are performed infinitely often, then operations will succeed infinitely often. (I.e., the system, as a whole, makes progress, even if some thread(s) starve.) Equivalently, a non-blocking progress guarantee simply states that it is impossible for /all/ threads to block forever. In your example, the fact that a range query is blocked by updates is not a problem, because the updates make progress.
- Non-blocking k-ary Search Trees, Trevor Brown, Joanna Helga
- Range Queries in Non-blocking k-ary Search Trees, Trevor Brown, Hillel Avni