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.