Home assignment # 3

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.

  1. Prove the algorithm’s correctness.
  2. 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.

Submission date: 22/01/2001