Skiplists and balanced search

Prev: Concurrent hashing and natural parallelism Next: Priority Queues

Exercises

Exercise 14.1. Recall that a skiplist is a probabilistic data structure. Although the expected performance of a contains() call is $O(\log n)$, where $n$ is the number of items in the list, the worst-case performance could be $O(n)$. Draw a picture of an eight-element skiplist with worst-case performance, and explain how it got that way.

---

Exercise 14.2. You are given a skiplist with probability $p$ and MAX_LEVEL $M$. If the list contains $N$ nodes, what is the expected number of nodes at each level from $0$ to $M-1$?

---

Exercise 14.3. Modify the LazySkipList class so find() starts at the level of the highest node currently in the structure, instead of the highest level possible, MAX_LEVEL.

---

Exercise 14.4. Modify the LazySkipList to support multiple items with the same key.

---

Exercise 14.5. Suppose we modify the LockFreeSkipList class so that on line 102 of Fig. 14.12, remove() restarts the main loop instead of returning false.

Is the algorithm still correct? Address both safety and liveness issues. That is, what is an unsuccessful remove() call’s new linearization point, and is the class still lock-free?

---

Exercise 14.6. Explain how in the LockFreeSkipList class a node might end up in the list at levels 0 and 2, but not at level 1. Draw pictures.

---

Exercise 14.7. Modify the LockFreeSkipList so that the find() method snips out a sequence of marked nodes with a single compareAndSet(). Explain why your implementation cannot remove a concurrently inserted unmarked node.

---

Exercise 14.8. Will the add() method of the LockFreeSkipList work even if the bottom level is linked and then all other levels are linked in some arbitrary order? Is the same true for the marking of the next references in the remove() method; the bottom-level next reference is marked last, but references at all other levels are marked in an arbitrary order?

---

Exercise 14.9. (Hard) Modify the LazySkipList so that the list at each level is bidirectional, and allows threads to add and remove items in parallel by traversing from either the head or the tail.

---

Exercise 14.10. Figure 14.17 shows a buggy contains() method for the LockFreeSkipList class. Give a scenario where this method returns a wrong answer.

Hint: The reason this method is wrong is that it takes into account keys of nodes that have been removed.

boolean contains(T x) {
  int bottomLevel = 0;
  int key = x.hashCode();
  Node<T> pred = head;
  Node<T> curr = null;
  for (int level = MAX_LEVEL; level >= bottomLevel; level--) {
    curr = pred.next[level].getReference();
    while (curr.key < key) {
      pred = curr;
      curr = pred.next[level].getReference();
    }
  }
  return curr.key == key;
}

Prev: Concurrent hashing and natural parallelism Next: Priority Queues