The relative power of primitive synchronization operations

Prev: Foundations of shared memory Next: University of consensus

Exercises

Exercise 5.1. Prove Lemma 5.1.5, that is, that every $n$ -thread consensus protocol has a bivalent initial state.

Exercise 5.2. Prove that in a critical state, one successor state must be 0-valent, and the other 1-valent.

Exercise 5.3. Show that if binary consensus using atomic registers is impossible for two threads, then it is also impossible for $n$ threads, where $n > 2$ . Hint: argue by reduction. If we have a protocol to solve binary consensus for $n$ threads, then we can transform it into a two-thread protocol.

Exercise 5.4. Show that if binary consensus using atomic registers is impossible for $n$ threads, then so is consensus over $k$ values, where $k > 2$ .

Exercise 5.5. Show that with sufficiently many $n$ -thread binary consensus objects and atomic registers, one can implement $n$ -thread consensus over $n$ values.

Exercise 5.6. Consider the following algorithm for two-thread binary consensus.

public class ConsensusProposal {
  boolean proposed = new boolean[2];
  int speed = new Integer[2];
  int position = new Integer[2];
 
  public ConsensusProposal() {
    position[0] = 0;
    position[1] = 0;
    speed[0] = 3;
    speed[1] = 1;
  }
 
  public decide(Boolean value) {
    int i = myIndex.get();
    int j = 1 - i;
    proposed[i] = value;
    while (true) {
      position[i] = position[i] + speed[i];
      if (position[i] > position[j] + speed[j])
        return proposed[i];
      else if (position[i] < position[j])
        return proposed[j];
    }
  }
}

Show that the algorithm is consistent and valid, that is, an output value must be an input of one of the threads, and the output values cannot differ.
Since the algorithm is consistent and valid and only uses read-write registers, it cannot be wait-free. Give an execution history that is a counterexample to wait-freedom.

Exercise 5.7. The Stack class provides two methods: push(x) pushes a value onto the top of the stack, and pop() removes and returns the most recently pushed value. Prove that the Stack class has consensus number exactly 2.

Exercise 5.8. Suppose we augment the FIFO Queue class with a peek() method that returns but does not remove the first element in the queue. Show that the augmented queue has infinite consensus number.

Exercise 5.9. Consider three threads, A, B, and C, each of which has an MRSW register, $X_{A}$ , $X_{B}$ , and $X_{C}$ , that it alone can write and the others can read. Each pair also shares a RMWRegister that provides a compareAndSet() method: A and B share $R_{A B}$ , B and C share $R_{BC}$ , and A and C share $R_{A C}$ . Only the threads that share a register can call that register’s compareAndSet() method or read its value.

Either give a three-thread consensus protocol and explain why it works, or sketch an impossibility proof.

Exercise 5.10. Consider the situation described in Exercise 5.9 except that A, B, and C can apply a double compareAndSet() to both registers at once.

Exercise 5.11. In the consensus protocol shown in Fig. 5.7, what would happen if we announced the thread’s value after dequeuing from the queue?

Exercise 5.12. Objects of the StickyBit class have three possible states, $⊥$ , 0, 1, initially $⊥$ . A call to write(v), where $v$ is 0 or 1, has the following effects:

If the object’s state is $⊥$ , then it becomes $v$ .
If the object’s state is 0 or 1, then it is unchanged.

A call to read() returns the object’s current state.

Show that such an object can solve wait-free binary consensus, that is, all inputs are 0 or 1, for any number of threads.
Show that an array of $lo g_{2} m$ StickyBit objects with atomic registers can solve wait-free consensus for any number of threads when there are $m$ possible inputs. Hint: give each thread one atomic multi-reader single-writer register.

Exercise 5.13. The SetAgree class, like the Consensus class, provides a decide() method whose call returns a value that was the input of some thread’s decide() call. However, unlike the Consensus class, the values returned by decide() calls are not required to agree. Instead, these calls may return no more than $k$ distinct values. When $k$ is 1, SetAgree is the same as consensus.

What is the consensus number of the SetAgree class when $k > 1$ ?

Exercise 5.14. The two-thread approximate agreement class for a given $ε > 0$ is defined as follows: threads A and B each call decide(x_a) and decide(x_b), where $x_{a}$ and $x_{b}$ are real numbers. These method calls respectively return values $y_{a}$ and $y_{b}$ such that $y_{a}$ and $y_{b}$ both lie in the closed interval $[min (x_{a}, x_{b}), max (x_{a}, x_{b})]$ , and $∣ y_{a} - y_{b} ∣ \leq ε$ . Note that this object is nondeterministic.

What is the consensus number of the approximate agreement object?

Exercise 5.15. An A2Cas object represents two locations for values that can be read individually and modified by a2cas(). If both locations have the corresponding expected values $e_{0}$ and $e_{1}$ , then a call to a2cas(e0, e1, v) will write $v$ to exactly one of the two locations, chosen nondeterministically.

What is the consensus number of the a2cas() object? Prove your claim.

Exercise 5.16. Consider a distributed system where threads communicate by message passing. A type A broadcast guarantees:

every nonfaulty thread eventually gets each message,
if P broadcasts $M_{1}$ and then $M_{2}$ , then every thread receives $M_{1}$ before $M_{2}$ ,
messages broadcast by different threads may be received in different orders at different threads.

A type B broadcast guarantees:

every nonfaulty thread eventually gets each message,
if P broadcasts $M_{1}$ and Q broadcasts $M_{2}$ , then every thread receives $M_{1}$ and $M_{2}$ in the same order.

For each kind of broadcast:

give a consensus protocol if possible;
otherwise, sketch an impossibility proof.

Exercise 5.17. Consider the following two-thread QuasiConsensus problem.

Two threads, A and B, are each given a binary input. If both have input $v$ , then both must decide $v$ . If they have mixed inputs, then either they must agree, or B may decide 0 and A may decide 1, but not vice versa.

Here are three possible exercises. Only one of them works:

Give a two-thread consensus protocol using QuasiConsensus showing it has consensus number at least 2.
Give a critical-state proof that this object’s consensus number is 1.
Give a read-write implementation of QuasiConsensus, thereby showing it has consensus number 1.

Exercise 5.18. Explain why the critical-state proof of the impossibility of consensus fails if the shared object is, in fact, a Consensus object.

Exercise 5.19. A team consensus object provides the same decide() method as consensus. A team consensus object solves consensus as long as at most two distinct values are ever proposed. If more than two are proposed, any result is allowed.

Show how to solve $n$ -thread consensus, with up to $n$ distinct input values, from a supply of team consensus objects.

Exercise 5.20. A trinary register holds values $⊥$ , 0, 1, and provides compareAndSet() and get() methods with the usual meaning. Each such register is initially $⊥$ . Give a protocol that uses one such register to solve $n$ -thread consensus if the inputs of the threads are binary, that is, either 0 or 1.

Can you use multiple such registers, perhaps with atomic read-write registers, to solve $n$ -thread consensus even if the threads’ inputs are in the range $0.. 2^{K} - 1$ for $K > 1$ ? You may assume an input fits in an atomic register. Important: remember that a consensus protocol must be wait-free.

Devise a solution that uses at most $O (n)$ trinary registers.
Devise a solution that uses $O (K)$ trinary registers.

Feel free to use all the atomic registers you want.

Exercise 5.21. Earlier we defined lock-freedom. Prove that there is no lock-free implementation of consensus using read-write registers for two or more threads.

Exercise 5.22. The following code shows a FIFO queue implemented with read(), write(), getAndSet(), that is, swap, and getAndIncrement() methods. You may assume this queue is linearizable, and wait-free as long as deq() is never applied to an empty queue. Consider the following sequence of statements:

class Queue {
  AtomicInteger head = new AtomicInteger(0);
  AtomicReference items[] = new AtomicReference[Integer.MAX_VALUE];
 
  void enq(Object x) {
    int slot = head.getAndIncrement();
    items[slot] = x;
  }
 
  Object deq() {
    while (true) {
      int limit = head.get();
      for (int i = 0; i < limit; i++) {
        Object y = items[i].getAndSet();
        if (y != null)
          return y;
      }
    }
  }
}

Both getAndSet() and getAndIncrement() methods have consensus number 2.
We can add a peek() simply by taking a snapshot of the queue and returning the item at the head of the queue.
Using the protocol devised for Exercise 5.8, we can use the resulting queue to solve $n$ -consensus for any $n$ .

We have just constructed an $n$ -thread consensus protocol using only objects with consensus number 2.

Identify the faulty step in this chain of reasoning, and explain what went wrong.

Exercise 5.23. Recall that in our definition of compareAndSet(), we noted that strictly speaking, compareAndSet() is not an RMW method for $f_{e, u}$ , because an RMW method would return the register’s prior value instead of a Boolean value. Use an object that supports compareAndSet() and get() to provide a new object with a linearizable NewCompareAndSet() method that returns the register’s current value instead of a Boolean.

Exercise 5.24. Define an $n$ -bounded compareAndSet() object as follows: it provides a compareAndSet() method that takes two values, an expected value $e$ and an update value $u$ . For the first $n$ times compareAndSet() is called, it behaves like a conventional compareAndSet() register: if the object value is equal to $e$ , it is atomically replaced with $u$ , and the method call returns true. If the object value $v$ is not equal to $e$ , then it is left unchanged, and the method call returns false, along with the value $v$ . After compareAndSet() has been called $n$ times, however, the object enters a faulty state, and all subsequent method calls return $⊥$ .

Show that an $n$ -bounded compareAndSet() object for $n \geq 2$ has consensus number exactly $n$ .

Exercise 5.25. Provide a wait-free implementation of a two-thread $(2, 3)$ -assignment object from three compareAndSet() objects, that is, objects supporting the operations compareAndSet() and get().

Exercise 5.26. In the proof of Theorem 5.5.1, we claimed that it is enough to show that we can solve 2-consensus given two threads and a $(2, 3)$ -assignment object. Justify this claim.

Exercise 5.27. We can treat the scheduler as an adversary who uses the knowledge of our protocols and input values to frustrate our attempts at reaching consensus.

One way to outwit an adversary is through randomization. Assume that there are two threads that want to reach consensus, each of which can flip an unbiased coin, and that the adversary cannot control future coin flips but can observe the result of each coin flip and each value read or written. The adversary scheduler can stop a thread before or after a coin flip or a read or write to a shared register. A randomized consensus protocol terminates with probability arbitrarily close to 1, given sufficiently long time, against an adversary scheduler.

The following is a plausible-looking randomized binary consensus protocol. Give an example showing that this protocol is incorrect.

Object prefer[2] = {null, null};
 
Object decide(Object input) {
  int i = Thread.getID();
  int j = 1 - i;
  prefer[i] = input;
  while (true) {
    if (prefer[j] == null) {
      return prefer[i];
    } else if (prefer[i] == prefer[j]) {
      return prefer[i];
    } else {
      if (flip()) {
        prefer[i] = prefer[j];
      }
    }
  }
}

Does the algorithm satisfy the safety properties of consensus, that is, validity and consistency? Is it true that each thread can only output a value that is the input of one of the two threads, and also that the outputs cannot be different?
Does it terminate with a probability arbitrarily close to 1?

Exercise 5.28. One can implement a consensus object using read-write registers by implementing a deadlock-free or starvation-free mutual exclusion lock. However, this implementation provides only dependent progress, and the operating system must make sure that threads do not get stuck in the critical section so that the computation as a whole progresses.

Is the same true for obstruction-freedom, the nonblocking dependent progress condition? Show an obstruction-free implementation of a consensus object using only atomic registers.
What is the role of the operating system in the obstruction-free solution to consensus? Explain where the critical-state proof of the impossibility of consensus breaks down if we repeatedly allow an oracle to halt threads so as to allow others to make progress.

Hint: think of how you could restrict the set of allowed executions.

Prev: Foundations of shared memory Next: University of consensus

Takashi's Notes

Explorer

The relative power of primitive synchronization operations

The relative power of primitive synchronization operations

Exercises

Graph View

Table of Contents

Backlinks