0%

specification

• no duplicate key

• deleting non-existent key leads to return false

• leaf-oriented BST

• all keys currently in the dictionary are stored in the leaves of the tree.
• Internal nodes of the tree are used to direct a Find operation along the path to the correct leaf.
• The keys stored in internal nodes may or may
not be in the dictionary.

features

• non-blocking

• linearizable

for every execution, one can assign a linearization point to each completed operation and some of the uncompleted operations so that the linearization point of each operation occurs after the operation starts and before it ends, and the results of these operations are the same as if they had been performed sequentially, in the order of their linearization points.

basic idea

splicing that parent out of the tree。一旦被标记，那么其指向子结点的指针将不能被改变。

solutions

using a separate state ﬁeld of the node to mark or flag，而不是mark那个pointer。

• mark: node marked is unchangeable。
• flag: indicate that an update is trying to change a child pointer of the node.

mark和flag类似于加锁。

insert和delete

insert

Insert (C):

1. ﬂag node D’s parent, node B,
2. change the appropriate child pointer of node B,
3. unﬂag node B.

delete

Delete (C):

1. ﬂag C’s grandparent, node B,
2. mark C’s parent, node D,
3. change the appropriate child pointer of B,
4. unﬂag node B.

insert在完成第一步以后，在insert进行后续操作时，其他线程将不能够block insert。delete类似的，在完成第一二步以后也是。

summary

1. Excellent tutorial about helping mechanism!!!
2. 在树上面进行并发操作的时候，这篇论文中描述的问题其实大都是存在的，因此论文中的方法可以考虑用到其他树型结构上面。

references

1. Non-blocking Binary Search Trees, Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel