Takashi's Notes

University of consensus

5 min read

University of consensus

Prev: The relative power of primitive synchronization operations Next: Spin locks and contention

Exercises

Exercise 6.1. Consider a concurrent atomic PeekableStack(k) object: an atomic Stack with an added look operation. It allows each of threads to execute push() and pop() operations atomically with the usual LIFO semantics. In addition, it offers a look operation, the first calls of which return the value at the bottom of the stack, that is, the least recently pushed value that is currently in the stack, without popping it. All subsequent calls to look after the first return null. Also, look returns null when the Stack is empty.

  • Is it possible to construct a wait-free Queue, accessed by at most two threads, from an arbitrary number of PeekableStack(1) objects and atomic read-write registers? Prove your claim.
  • Is it possible to construct a wait-free -thread PeekableStack(2) object from an arbitrary number of atomic Stack objects and atomic read-write registers? Prove your claim.

Exercise 6.2. Give an example showing how the universal construction can fail for objects with nondeterministic sequential specifications.

Exercise 6.3. Propose a way to fix the universal construction of Fig. 6.8 to work for objects with nondeterministic sequential specifications.

Exercise 6.4. In both the lock-free and wait-free universal constructions, the sequence number of the sentinel node at the tail of the list is initially set to 1. Which of these algorithms, if any, would cease to work correctly if the sentinel node’s sequence number were initially set to 0?

Exercise 6.5. In the lock-free universal construction, every thread has its own view of the head pointer. To append a new method invocation, at line 14 of Fig. 6.4, a thread selects the furthest among these head pointers:

Node before = Node.max(head);

Consider changing this line to:

Node before = head[i];

Does the construction still work?

Exercise 6.6. Suppose, instead of a universal construction, you simply want to use consensus to implement a wait-free linearizable register with read() and compareAndSet() methods. Show how you would adapt this algorithm to do so.

Exercise 6.7. In the wait-free universal construction shown in Section 6.4, each thread first looks for another thread to help, and then tries to append its own node. Suppose that instead, each thread first tries to append its own node, and then tries to help the other thread. Explain whether this alternative approach works. Justify your answer.

Exercise 6.8. In the construction in Fig. 6.4, we use a distributed implementation of a head reference, to the node whose decideNext field it will try to modify, to avoid having to create an object that allows repeated consensus. Replace this implementation with one that has no head reference at all, and finds the next head by traversing down the log from the start until it reaches a node with a sequence number of 0 or with the highest nonzero sequence number.

Exercise 6.9. In the wait-free protocol, a thread adds its newly appended node to the head[] array on line 28 even though it may have already added it on line 26. This is done because, unlike in the lock-free protocol, it could be that the thread’s node was added by another thread on line 26, and that helping thread stopped at line 26 right after updating the node’s sequence number but before updating the head[] array.

  1. Explain how removing line 28 would violate Lemma 6.4.4.
  2. Would the algorithm still work correctly?

Exercise 6.10. Propose a way to fix the universal construction to work with a bounded amount of memory, that is, a bounded number of consensus objects and a bounded number of read-write registers.

Hint: add a before field to the nodes and build a memory recycling scheme into the code.

Exercise 6.11. Implement a consensus object that is accessed more than once by each thread using read() and compareAndSet() methods, creating a multiple-access consensus object. Do not use the universal construction.

Exercise 6.12. Your mission is to transform a sequential stack implementation into a wait-free linearizable stack implementation, without regard for questions of efficiency or memory use.

You are given a black-box Sequence type with the following methods. You can atomically append an item to the end of the sequence. For example, if the sequence is <1, 2, 3> and you append 4, the sequence becomes <1, 2, 3, 4>. This operation is wait-free and linearizable. If a concurrent thread tries to append 5, the sequence becomes either <1, 2, 3, 4, 5> or <1, 2, 3, 5, 4>. Note that Sequence items do not have to be integers: they can be any kind of object you like.

You can also iterate through the elements of a sequence. Here, we iterate through a sequence printing each value until we see the string "stop":

foreach x in s {
  if (x == "stop") break;
  System.out.println(x);
}

Note that if another thread is appending new values while you are iterating through a sequence, you might keep going forever.

Implement a wait-free linearizable stack using an atomic sequence object, and as much atomic read-write memory and sequential stack objects as you like. Your stack should support both push() and pop() operations with the usual meanings. Again, do not worry about efficiency or memory use.

Explain briefly why your construction is wait-free and linearizable, in particular identify the linearization points.

Prev: The relative power of primitive synchronization operations Next: Spin locks and contention

Graph View

Backlinks