Maximimal Independent Set on Ring and Path

Question

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.

Answer 1

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$.