Check out the errata page for the book.

# Question 1 [Attiya and Welch, Question 5.5]

Define the *k-set consensus* problem as follows. Each processor starts with some arbitrary integer value xi, and the output should be an integer value yi such that:

**Validity:** yi is one of {x0, … , xn-1}, and

**k-agreement:** the number of different output values is at most k.

Algorithm 5.4 (pdf) was proposed for solving the k-set consensus problem in the presence of f crash failures, for any f<n.

- Prove the algorithm’s correctness.
- Analyze the algorithm’s message complexity.

# Question 2 [Attiya and Welch, Question 15.3]

The consensus number of object X is n, denoted CN(X) = n, if n is the largest value for which X solves wait-free n-processor consensus.

Consider a shared memory system in which there are only test&set and read/write objects. Prove that CN(test&set) = 2.

# Question 3 [Attiya and Welch, Question]

Show that the consensus number of an extended queue, with an additional peek operation (reading the head of the queue without removing it), is infinite.

# Question 4 [Attiya and Welch, Question 15.13]

Consider the following modification to Algorithm 15.5 (wait-free simulation of arbitrary objects): First try to thread your own operation, and only then try to help other processors. Show that the modified algorithm is not wait-free.