Solutions to homework 3

Notice:
All solutions were provided by students. In observance of Swedish customs their identity is not disclosed (Elitism is not politically correct).

Q1.

(10 pts) Let each process p (we have n of them) follow these steps:

1.

Broadcast x_p.

2.

Receive n-k+1 assessments x_qi and sort them according to x_qi.

3.

Decide d_p:=max_i(x_qi).

The non-triviality condition holds, as is easy to see by considering the case when every p has x_p=0 versus the case when x_p=1. The bureaucracy is also limited, because we know there will be at least k processes that will send us messages, even when we loose k-1 processes. The agreement property is ensured for the following reason. If a process p decides on a value d, the maximum of the first n-k+1 received values, d will be among the k highest values. I.e., p may have missed k-1 assessments that are ranked higher than d, but he will at the worst catch the lowest d among k possible decision values. Fortunately, every process will pick decision values among exactly these k highes assessments, so we are ensured that at most k different decision values are chosen in the system.

Q2.

(10 pts) We start by showing that two events (p,m) and (q,n) always commute if $p\neq q$. Proof: We only have to show that the changes to the message buffer and the state vector are independent of the order, in which we apply the events. By the definition of a step, the changes that occur to the message buffer in a step are always the same, independent of the state vector. Now we examine how the state vector changes. Let S_p and S_q be the states of p and q respectively. If (p,m) is the first event, p will change its state from S_p to $S_p'=\delta_p(m,S_p)$ in the first step. In the second step q will change its state from S_q to $S_q'=\delta_q(n,S_q)$(since $p\neq q$, q's state is not affected by step one). On the other hand, if (q,n) is the first event, q will change its state to $\delta_q(n,S_q)$ in the first step, and since both n and S_q are the same as above and the transition function $\delta_q$ is deterministic, q's new state will be S_q'. By the same argument, p's new state will be S_p' after step two. This concludes the proof.

The above lemma actually implies the proof of the commutativity lemma, since if $\sigma=(p_1,m_1)\circ\cdots\circ(p_k,m_i)$ and $\rho=(q_1,n_1)\circ\cdots\circ(q_{\ell},n_{\ell})$ where $p_i\neq q_j$ for all (i,j) we have that $(p_i,m_i)\circ(q_j,n_j)=(q_j,n_j)\circ(p_i,m_i)$ for all pairs (i,j).

Q3.

(10 pts)
Each vertex v knows its color class $\chi(v)$, which we from now on will assume to be an integer in [c(n)]. Consider the following algorithm:

1.

For each color class $i=1, \ldots, c(n)$:

(a)

For $j=1, \ldots, d(n) + 1$:

i.

Each vertex in color class i sends the following information to all its neighbors: Its (j-1)-neighborhood, its color and a flag to indicate if any of its neighbors from a different cluster belong to the global MIS.

ii.

Any vertex which does not belong to color class i disregards any information that is being sent to it.

(b)

All vertices in each cluster of color i now knows the structure of the entire cluster they belong to, and use the same algorithm to find an MIS in it. All the cluster MIS's are added to the global MIS.

(c)

The vertices in the cluster MIS notify their neighbors that they were added to the global MIS.  

I claim that this will give an MIS. The reason for this is that all clusters of the same color will be dealt with separately -- there cannot exist any edges between such clusters -- and as each cluster is of diameter d(n), each process can execute the same algorithm. The interaction between the clusters is taken care of in step 1c, which guarantees that two adjacent edges belonging to different clusters cannot both be part of the MIS's in the two clusters.