Next: Homework 4 Up: Lecture Notes in Theoretical Previous: Homework 2

# Homework 3

Q1.
K-AGREEMENT
Consider the following generalization of the consensus problem in asynchronous systems (message passing). The input xp of each process p takes values in a set of size k+1 rather than in just 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 xp=v for all p then, dq=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 and be two runs of events where only processes in, respectively, S and R take steps. Then, for any configuration 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 Ci. 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 Ci and where (Ci,Cj) is an edge ()if and only if there is an edge (u,v) of G such that and .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.

Next: Homework 4 Up: Lecture Notes in Theoretical Previous: Homework 2
Viggo Kann
Sat Dec 20 23:41:16 MET 1997