Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I known this question is more appropriate to, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic methods is required.

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

The algorithm is:

Every node v executes the following code:
if all neighbors of v with larger identiers have decided not to join the MIS
  v decides to join the MIS
end if

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: The probability of time complexity $c\log n$ is given for MIS for a path and the exercise asks to find a time complexity and it's probability for a ring graph. Besides finding it for a ring I am interested in proving it for a path. 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.

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

I will appreciate any help in solving this exercise.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.