Suppose we have a system with $n$ processes. Certain pairs of processes are in conflict, meaning that they

both require access to a shared resource. In a given time interval, the goal is to schedule a large subset $S$

of the processes to run$-$the rest will remain idle$-$so that no two conflicting processes are both in the

scheduled set $S.$ We'll call such a set $S$ conflict$-$free. One can picture this process in terms of a graph $G=$

$(V,E)$ with a node representing each process and an edge joining pairs of processes that are in conflict.

It is easy to check that a set of processes $S$ is conflict$-$ free if and only if it forms an independent set in $G.$

This suggests that finding a maximum$-$size conflict$-$free set $S,$ for an arbitrary conflict $G,$ will be difficult

$($since the general Independent Set Problem is reducible to this problem$).$ Nevertheless, we can still look

for heuristics that find a reasonably large conflict$-$free set. Moreover, we'd like a simple method for

achieving this without centralized control: Each process should communicate with only a small number of

other processes and then decide whether or not it should belong to the set $S.$ We will suppose for

purposes of this question that each node has exactly $d$ neighbors in the graph $G.($That is$,$ each process is

in conflict with exactly d other processes.$).$

Consider the following simple protocol.

Each process $P_i$ independently picks a random value $x_i$; it sets $x_i$ to $1$ with probability $\frac{1}{2}$ and sets

$x_i$ to $0$ with probability $\frac{1}{2}.$ It then decides to enter the set $S$ if and only if it chooses the value $1,$

and each of the processes with which it is in conflict chooses the value $0.$

Prove that the set $S$ resulting from the execution of this protocol is conflict$-$free. Also, give a formula for

the expected size of $S$ in terms of $n($the number of processes$)$ and $d($the number of conflicts per

process$).$