scribe.tex

leach simulation by castaila simulator please read the documentation for further correspondence bye.

\documentclass{article}


\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
%\documentstyle[]{article}
\pagestyle{empty}

% \setlength{\topmargin}{ 0.25in}
% \setlength{\columnsep}{2.0pc}
% \setlength{\footheight}{0.0in}
% \setlength{\headheight}{0.0in}
% \setlength{\headsep}{0.0in}
% \setlength{\oddsidemargin}{-.19in}
% \setlength{\parindent}{1pc}
% \textheight 8.75in
% \textwidth 6.8in
\begin{document}
\title{\LARGE \bf Parallel Algorithm for Maximal Independent Set }
\author{T.Raghav }
\date{}
\maketitle
\thispagestyle{empty}
\bibliographystyle{unsrt}
\maketitle



Parallel algorithms are meant to do computation on P processors(in parallel), P polynomial function of input size n, and number of steps to completion by each of the processor is bounded by a ploylogarithmic function on n.
In this Parallel model of computation, Parallel computer has P processor, each having constant number of local registers which each processor can alone access. Each of the P processor may read from and write into any of the M global memory locations; these global memory location serve as the only mechanism for communication between the processors. Computation proceeds in a series of synchronous parallel steps. Assumption of synchrony, every processor finishes execution step i before any processor begins executing step i+1.




\section{Maximal Independent set}
Let G(V,E) be an undirected graph with n vertices and m edges. A subset of vertices I $\subseteq$ V is said to be independent in G if no edge in E has both its end-points in I. Equivalently, I is independent if for all v $\in$ I, N(v) $\cap$ I = \O{}. N(s) is the set of vertices in V that are adjacent to v and that the degree of v is d(v) = $\mid N(s)\mid$ 





An independent set is maximal if it is not properly contained in any other independent set in G. On a single processor finding Maximal independent set is easy.

Following algorithm  works out maximal independent set.



\begin{enumerate}
 \item  I = $\emptyset$, $V^{'}$ =  V.
 \item  While ( $V^{'} \neq \emptyset$ ) do
      \begin{enumerate}
        \item Choose any v $\in V^{'}$
        \item Set I = I$\cup$ v.
	\item Set $V^{'}$ = $V^{'} \setminus$ (v $\cup$ N(v)).
 	\end{enumerate}
\item   Output I.	
\end{enumerate}


Now, finding Maximal Independent set I, in parallel. The idea is to generalize the basic iterative step: find an independent set S, add S to I, and delete S $\cup$ N(s) from the graph. Each iteration has to complete fast in parallel, and also guarantee that total number of iteration is small. This is possible if we choose S such that S $\cup$ N(S) is large. if S $\cup$ N(S) is constant fraction of $\mid V^{'} \mid$, then we will guarantee to have only O (log$\mid V \mid$) rounds. 


Pick a large number of random vertices R $\subseteq $ V. R may or may not be independent, sampling in favor of lower degree vertices will ensure that there are few edges with both end points in R.
\\
\\
Example:\\
\\
Let $R$ be chosen randomly, $a,b \in R$\\
total number of edges induced by $R$ = 20\\
deg(a) = 4 , deg(b) = 10 \\
number of edges incident on $a$ = deg(a) = 4\\
number of edges incident on $b$ = deg(b) = 10\\
Pro(edge induced by R is incident on a) = 4 / 20\\
Pro(edge included by R is incident on b) = 10 / 20\\
\hspace{1 cm}choose $a$ because in the induced graph R, probability of $a$ being independent is large as it has few number of edges which may be adjacent to other vertices when compared to $b$.



To obtain the independent set from $R$ we consider each edge of this type and drop the end point of lower degree. This results in an independent set, and the choice of the end point retained for $S$ ensure that $N(S)$ is likely to be large.


\section{Algorithm Parallel MIS:}
Input: Graph G(V,E), n processes for each vertex, m processes for each edge.\\
Output: A maximal independent set $I \subseteq V$


\begin{enumerate}
 \item  $I = \emptyset$.
 \item  repeat
\begin{enumerate}
 \item[2.1]  for all $v \in V$ do (in parallel)\\
 \hspace{2 cm} if $d(v) = 0$ then add $v$ to $I$ and delete $v$ from $V$\\
 \hspace{2 cm} else mark $v$ with probability $\frac{1}{2d(v)}$
\item[2.2]  for all $(u,v) \in E$ do (in parallel)\\ 
 if both $u$ and $v$ are marked\\
 then unmark the lower degree vertex.
\item[2.3] for all $v \in E$ do (in parallel)\\
 if $v$ is marked then add $v$ to $S$.
\item[2.4] $I = I \cup S$.
\item[2.5] delete $S \cup N(S)$ from $V$, and all incident edges from E.

\end{enumerate}
until V = $\emptyset$
\end{enumerate}

claim  : Each iteration of the Parallel MIS algorithm can be implemented in O(log n) time using EREW(exclusive read and exclusive write) with O(n + m ) processors.

Assumption - There is a initial order assigned to the vertices and edges(and corresponding processors)

step 2.2 - O(log m) each edge maintains a bit string of size = number of vertices. We can formulate reverse binary tree, end of the iteration the last node in the order assigned initially will give the set containing independent set of the current iteration.\\
\\
Following fig shows the procedure
\begin{center}
 \includegraphics[scale = 0.5]{3.eps}
 % 3.eps: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=20 20 575 437
\end{center}


N(S) can also be computed in O(log m) steps by the same procedure of reverse tree, but now do ``or '' of bit string.
At the end of iteration the last indexed node gives S U N(S)


Following fig shows the procedure 
\begin{center}
 \includegraphics[scale = 0.5]{4.eps}
 % 4.eps: 1179666x1310738 pixel, 300dpi, 9987.84x11097.58 cm, bb=20 20 575 437
\end{center}

Now the remaining is to compute the degree of each vertex $v \in V - S U N(S)$. This can also be done in $O(log m)$ steps, use addition(``+'') operator in place of ``or''. At the end of iteration, the bit string shows how many edges each vertex has lost and form there we can compute the new degree of each of the remaining vertices.
\\
\\ 




claim : Expected number of iterations is O(log n)



S - independent set in current iteration\\


claim 1 : Pro( $w \in S \mid w$ is marked) $\geq$ 1/2( one iteration)\\

$$\Longrightarrow\:\:\Pr(w \notin S \mid w \:is \:marked)$$\\
$$\Longrightarrow\:\:\Pr(\exists a \: higher \: degree \:neighbor \:of \:w \:that \:is \:marked)$$
$$\Longrightarrow\:\:\sum_{\substack{w^{'} :\: w^{'}\: is\: a\: higher\\ degree\: neighbor \\ of\: w}} \hspace{1 cm}     \frac{1}{2 deg(w^{'})} $$
$$\Longrightarrow\:\: \leqslant\:\:\sum_{\substack{w^{'} :\: w^{'}\: is\: a\: \\neighbor \: of\: w}} \hspace{1 cm}     \frac{1}{2 deg(w^{'})} $$

$$ \because \:\:N(w)\: = \:deg(w) $$
$$\Longrightarrow\:\:\frac{deg(w)}{2deg(w)} = \frac{1}{2}$$
$$\therefore\:\:\Pr(w \in S \mid w \:is \:marked) \geq \frac{1}{2}$$
\\



A vertex $v \in V$ is GOOD if it has at least $\frac{deg(v)}{3}$ neighbors of degree no more that $deg(v)$; otherwise, the vertex is BAD. An edge is GOOD if at least one of its end-points is a good vertex, and it is bad if both end-points are bad vertices.
\\



Let $u$ be good vertex  \\
$$\Pr(\exists \:v\: \in \:N(u) \:gets \:marked\:\mid \:u \:is \:good \:vertex\:)$$
$$=\:1\: -\: \Pr\:(\:no\: N(u)\: gets \:marked\:)$$
$$=\:1\:-\:\prod_{\substack{v\::\:v \:\in \:N(u)}} (1\: - \: \frac{1}{2deg(v)})$$
$$\geq\:1 -\:\: \prod_{\substack{v\::v\:\in\:N(u) \\ deg(v) \:\leqslant\: deg(u)}} \:(1\: - \: \frac{1}{2deg(v)})$$
$$\geq\:1\:-\: \prod_{\substack{v\::v\:\in\:N(u) \\ deg(v) \:\leqslant\: deg(v)}} \:(1\: - \: \frac{1}{2deg(v)})$$
$$=\:1\:-\:(1\: - \: \frac{1}{2deg(v)})^{\frac{deg(v)}{3}}$$
$$\geq \:(1\:-\: e^{\frac{-1}{6}})$$


$$\therefore\:\Pr(u \in N(S)) \geq \frac{(1\:-\: e^{\frac{-1}{6}})}{2}$$


Let $\alpha \:=\:\frac{(1\:-\: e^{\frac{-1}{6}})}{2}  $ \\
i.e if v is good then probability that v gets deleted in an iteration is at least $\alpha$
\\
\\
\\
claim : At least $\frac{1}{2}$ of the edges are good in a graph in any iteration.\\
proof: Denote set of bad edges by $E_{B}$. define f: $E_{B} \rightarrow E \times E$ so that for all $e_{1} \neq e_{2} \in E_{B}$, $f(e_{1}) \cap f(e_{2}) = \emptyset$. This proves $\mid$ $E_{B}| \leqslant |E|/2$, and we're done.
\\
\\
The function $f$ is defined as follows. For each $(u,v)$ $\in E$,direct it to the higher degree vertex. Break ties arbitrarily. Now suppose $(u,v)$ $\in E_{B}$, and is directed towards v. Since v is BAD, it has at least $\frac{2deg(V)}{3}$ edges going out of v and at most $\frac{deg(v)}{3}$ coming into v. Hence we can pair every incoming edge with a unique pair edges leaving out of v. This gives our mapping.

\begin{center}
 \includegraphics[scale = 0.4]{2.eps}
 % Screenshot.png: 1280x800 pixel, 72dpi, 45.16x28.22 cm, bb=0 0 1280 800
\end{center}
$$\Pr(\:good\:edge\:e\:=\:(u,v)\:is\:removed\:in\:an\:iteration\:)$$
$$\geq\Pr(\:a\:good\:vertex\:u\:is\:removed \:in\:a\:iteration)\:= \:\alpha  $$



Expected number of edges in the graph after deletion of $N(S) \cup S$ \\


Let $X_{i}$ an indicator random variable for each edge $e_{i}$\\

$X_{i}$ = 1 if $e_{i}$ is retained\\

    \hspace{1 cm}  = 0 otherwise\\


E[$\sum X_{i}$] = $\sum_{i \in E} \Pr[e_{i} \: is \: retained]$\\


$=\:\sum_{bad\: e}\Pr(e\: is \:retained]\: + \: \sum_{good\: e}\Pr[e\:is\:retained]$\\




$\leqslant \:m_{1}\: +\: m_{2}(\:1\: -\: \alpha\:)\:=\: m\: -\: m_{2}\alpha \:\leqslant\: m \:-\:\frac{m\alpha}{2 }\:=\:m\:(\:1\:-\:\frac{\alpha}{2}\:)$\\



$\therefore$ the expected number of iterations is $O(log_{\alpha} n)$
      

 




\begin{center}
 \includegraphics[width= 300 pt, height = 300 pt]{1.eps}
 % a.png: 960x720 pixel, 96dpi, 25.40x19.05 cm, bb=0 0 720 540
\end{center}






\end{document}