Maximimal Independent Set on Ring and Path

Let's consider distributed version of algorithm for finding MIS of any graph $A$.

For details, MIS - Maximimal Independent Set.

Slow version of distributed algorithm for MIS, page 2 - Distributed algorithms. Maximal Independent Set

In worst case, time complexity of the algorithm is $\text{O}(n)$ and a message complexity is $\text{O}(m)$. If nodes of the network are not unique than it's not possible to find MIS.

I am interested in few special cases, when the graph is a path and ring.

Exercise: Consider a path graph $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$, time complexity of MTS_Slow is $T \leq c\log n$ for a constant $c$ with probability $1-\frac{1}{n}$. What is a time complexity and it's probability on a ring $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$.

Ideas: Time complexity has $\log n$ factor, therefore on each phase number of candidates for MIS nodes from a path graph $G$ should be divided by constant factor. Lets consider the worst case, when only one node is choicen to join MIS on each phase, it occurs when the nodes' UID's are located in increasing or decreasing order, it happes with probability $P(B)=\frac{1}{2^n}$, $P(A)=\frac{1}{2}$, where B - nodes' UID is placed in increasing order, A - the next node's UID is bigger the the current one. But how to show that the number of candidates is getting lower by any arbitrary constant factor. The problem is I have a difficulties in defining probability for taking arbitrary constant factor of nodes on each phase.

Case with ring should be similar to a path graph case.

I will appreciate any help in solving this exercise.

-
have a look at the fastmis_v2 in the same chapter. – AJed Jan 8 '13 at 14:36
may I know how you got MIS_Slow in a path is $O(\log n)$ on average ? – AJed Jan 9 '13 at 15:17
@AJed, $\text{O} ( \log n )$ on average on a path is given for an exercise. I am also very curious how to derive it. – tam Jan 14 '13 at 13:12
To be honest with you, i have an answer but I dont want to include it because I dont know its correctness yet. What you can do is to find the average number of nodes that are larger than all neighbors. You can find that by calculating the probability that a node is larger than both its two neighbors. Then, by computing this number you know an estimate of how many nodes are deleted in each iteration of the algorithm. There will be a constant factor ($c < 1$). Therefore, you can realize that the number of iteration is $O(\log n)$. I dont have the precise value of $c$ though. – AJed Jan 14 '13 at 15:14
@AJed, thanks for the hint, the node is larger than 2 it's neighbors with probability $\frac{1}{4}$. Each iteration there are $\frac{n}{4}$ such nodes, and $\frac{n}{2}$ edges to be deleted, and in order to delete all edges it will take $\text{O}(\log n)$. Does it make sense? – tam Jan 14 '13 at 16:53

if a node terminates the algorithm after an iteration with probability $1/c$, then after $k$ iterations this probability is $c^{-k}$. and the number of iterations required is $\ln _c n$. This is done by arguing that the expected number of nodes after $k$ iterations is $n c ^{-k}$, and we want to make this value less or equal to 1. We achieve this by setting $k$ to $\ln _c n$.
Therefore, replacing $k = \ln _c n$ leads to $c^{- \ln _c n} = 1/n$, and whence the probability of correctness is $1 - 1/n$.
How to find $c$ ? As I said in my comment, I truly dont know the exact value. Here is a solution. Someone else may correct me.
We should calculate the probability that a node $v$ terminates the algorithm in any given iteration. This happens if $v$ is greater than its two neighbors OR if the left neighbor of $v$ is greater than all its neighbors OR if the right neighbor of $v$ is greater than all its neighbors. The probability of any of these events is 1/2*1/2 = 1/4. The probability of any of these events is 1/4 + 1/4 + 1/4 = 3/4. Therefore $c = 3/4$.