A Practical Concurrent Binary Search Tree (PPoPP'10)
Nathan G. Bronson, Jared Casper, Hassan Chafi and Kunle Olukotum
Computer Systems Laboratory, Stanford University
Description
Abstract: |
Questions
Question 1:
Describe how the node version numbers are used to validate that a read performed at time t1 is still valid at time t2.
Question 2:
Summarize the hand-over-hand optimistic validation protocol.
Andreas
Q1: Q2: |
Jonatan
Q1: "at t1 read the associated version number v1, blocking until the change bit is not set; read the protected value x; then at t2 reread the version number v2. If v1 = v2, then x was still valid at t2." Q2: Separate version numbers are kept for the left and right child link. The hand over hand validation is like hand over hand locking, but applied to version numbers. To navigate through a node, the parent link and its version is read. Thereafter, the child link and its version number is read. Thereafter the parent version is validated. If still valid, it's ok to proceed descending. |
Martin
Q1: The version number is changed when the node is changed. So at time t1, one first reads the version Q2: While traversing nodes in the tree, it will check the validity of each link by the version numbers |
Kjell
Q1: To check that a read of a node performed at t0 is still valid at t1 the version number is read before t0 and then again after t1. If the the version number has not changed between the reads, the read of the the node performed at t0 is still valid at t1. Q2: The links between nodes have version numbers. At time t0 (before traversing link X), the version number of link X is read. Link X's version number is read again at time t1 after the value of the node at the end of link X has been read. The value of the link version number read at t0 and t1 is compared (after t1). Based on the comparison it is decided if the algorithm shall backtrack to the previous node or not. |
Pan
Q1: If the version numbers are the same at t1 and t2, it means the read performed at t1 is still valid at t2. A changing bit is used to indicate the data is being written. When reading the version number, the operation blocks until the changing bit is not set (no one is writing the data). |
Sofia
Q1: At t1 the version number is read, then the protected value. At t2 the version number is read again. If it is the same as the version number at t1, then the read at t1 is still valid. Q2: In the tree, links are marked with version numbers to track changes to left and right child nodes. Links are validated as in Q1. In order to pass through a node, both the incoming and outgoing edge must be valid at the same time, so the incoming edge is validated after the outgoing edge. |
Afshin
Q1. To perform a read at time t1 and verify that the read is still valid at t2: at t1 read the associated version number v1, blocking until the change bit is not set; read the protected value x; then at t2 reread the version number v2. If v1 = v2 then x was still valid at t2. Q2. There is an implicit state of a search, which is an open interval of keys that must either be absent from the entire tree or present in the current subtree. Each time that the search process performs a comparison and navigates downward, the interval is reduced. At all times the interval includes the target key, so if the subtree ever becomes empty we can conclude that no node with that key is present. |
Yunyun
Q1: If the version numbers v1 (at time t1) and v2 (at time t2) are the same, then the value read at t1 is still valid at t2. Q2: The left and the right links of each node are marked with version numbers. To validate the search of a node, both links of the node must be validated as described above. If the node is valid, then the search can pass. Otherwise, it has to backtrack. |
Stavros
Q1: Reading sequence: Read version number -> wait until change bit is reset -> read data -> re-read version number and compare. In this way, any changes that happen will be noticed by the difference in the version numbers. Q2: The commit action of each transaction happens after the initialization action of the next transaction. Therefore a failing transaction will conceptually undo the commit of the previous, which will then have to be retried. |