Maximum independent set on the ring could be found by distributed algorithm like following (unique UID's is required).
Every node v executes the following code:
if all neighbors of v with larger identiers have decided not to join the MIS
then
v decides to join the MIS
end if
It's obvious that when UID's is a monotonic sequence, this distributed version works like sequential version of algorithm. Only one node joins MIS on every phase. On the average case when UID's is uniformly distributed among nodes, few nodes might join MIS on the same round.
The problem is what is the expected number of phases when all UID's is just random permutation, in other words how long it could take to build MIS when UID's are random permutation.
Let's consider some sequence of $m$ nodes following one by one. The probability that this sequence is monotonic is $\frac{1}{m!}$.
The probability that such sequence exists in the ring is $\leq \frac{n}{k!}$ by Boole's inequality, when the sequence can start from one of $n$ nodes.
The problem is I cannot get how to derive time complexity with the above data. It looks like I missed something.
If you have any idea how to approach the solution, please, share with us.
