Homework 3

Q1.

K-AGREEMENT
Consider the following generalization of the consensus problem in asynchronous systems (message passing). The input x_p of each process p takes values in a set of size k+1 rather than in just $\{0,1\}$ as before. The problem is to find a fault tolerant protocol under the following amended notion of agreement:

k-agreement: The set D of decision values has cardinality at most k.

While the notion of Limited Bureaucracy remains the same, Non Triviality is generalized in the obvious way: if x_p=v for all p then, d_q=v for every correct process q. Give a (k-1)-resilient protocol for k-agreement.

Q2.

YAWN!
Give a crisp and concise proof of the following Lemma, which was stated in class:

COMMUTATIVITY LEMMA. Let S and R be two disjoint sets of processes and let $\sigma$ and $\rho$ be two runs of events where only processes in, respectively, S and R take steps. Then, for any configuration C, $\sigma \rho (C) = \rho \sigma (C)$.

Does the same lemma hold for synchronous systems?

Q3.

NETWORK DECOMPOSITION
A cluster decomposition of a graph G is a partition of G into connected components C_i. Given a graph G and a cluster decomposition, the cluster graph of G, denoted by C(G), is a graph whose vertices are the clusters C_i and where (C_i,C_j) is an edge ($i \neq j$)if and only if there is an edge (u,v) of G such that $u \in C_i$ and $v \in C_j$.Finally, a (c(n),d(n))-decomposition of G is a cluster decomposition such that

1.

Each cluster has diameter at most d(n) (the diameter of a cluster is a the maximum distance between any two nodes in the cluster);

2.

The chromatic number of the cluster graph is at most c(n).

Show that given a (c(n),d(n))-decomposition it is possible to compute a maximal independent set in O(c(n) d(n)) rounds in the distributed model of computation.