Slow MIS Distributed Algorithm

I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$.

I investigate the Slow MIS distributed algorithm (from these lecture notes, page 2).

Following is the more detailed version than in lecture notes.

• Every node sends its UID to it's neighbors.
• Run procedure join

on event: getting a message decide(1) from a neighbor $w$ do

• Set $b = 0$ - flag that node terminates and not participating in further phases.

• Send decide(0) to all neighbors

on event: getting a message decide(0) from a neighbor $w$ do:

• Invoke procedure join.

Procedure Join

if every neighbor $w$ of $v$ with a larger identifier has decided $b(w) = 0$, then do

• Set $b = 1$.
• Send decided(1) to all neighbors.

The question is what's time complexity of the algorithm $\Theta(n)$ or $\Theta(D)$, where $D$ is a diameter of $G$.

In the lecture notes linked above, they say that time complexity is $O(n)$. I think that in our case it can be expressed as $\Theta(D)$ (simultaneously $O(D)$ and $\Omega(D)$) for special cases.

The problem is how to prove that that time complexity in general is $O(D)$ and there are special cases when time complexity is $\Omega(D)$ if it's right at all.

Let's take a look at the example I have in mind.

$D=1$ and $n=4$, and as I understood the algorithm every vertex will decide to join MIS on the first round.

If you have an idea how to show that, please, share it with us.

-
Is the time complexity the number of rounds? – adrianN Feb 1 '13 at 10:19
No, the running time is not bounded by $O(D)$. In your example, consider what happens if the nodes have identifiers $1, 2, ..., n$ from left to right. Round 1: node $n$ joins (everyone else just waits, as they have a neighbour with a higher identifier who has not decided yet). Round 2: node $n-1$ decides not to join (everyone else waits). Round 3: node $n-2$ decides to join, etc. It takes linear-in-$n$ time, even though you have a constant diameter. – Jukka Suomela Feb 1 '13 at 11:07
@JukkaSuomela, thank you very much for your comment! The problem is I need to show that the time complexity is either $\Theta(D)$ or $\Theta(n)$. I assume it's $\Theta(D)$, which means $O(D)$ in some cases and $\Omega(D)$ in other cases. Case with $O(D)$ is obvious I think, but the case with $\Omega(D)$ is less obvious, time complexity of the above example is $\Omega(D)$, therefore in total we have $\Theta(D)$ time complexity. Does it make sense? – fog Feb 1 '13 at 12:13
@adrianN, yes, the time complexity is the number of rounds. – fog Feb 1 '13 at 12:16
@fog: "I need to show"? Is this a homework problem? – Jukka Suomela Feb 1 '13 at 14:04

It is not actually the diameter. It is the longest chain in the partial order $P$ of the input graph $G = (V,E)$. The poset $P$ is constructed as follows. Given an input graph $G = (V,E)$ such that each vertex has a unique identifier. Build an oriented graph $G' = (V,E')$ such that an edge $(u,v) \in E'$ if $(u,v) \in E$ and $u \succ v$. Then build a partial order $P$ of $G'$ by taking the transitive closure of $G'$. Let $l$ be the length the longest chain of $P$, then the time complexity of your algorithm is exactly $l$ (assuming here that the time complexity is measured by the number of communication rounds and in each round a node can send/receive a message to/from all its neighbors). Note that $l$ is $\in O(n)$ and in $\Omega(1)$.

What about average complexity ? Let's $G(n,p)$ be a random graph of $n$ vertices and an edge between any pair of nodes exist with probability $p \in [0,1]$. Then, if you build a partial order $P$ of this graph (called random graph order), you will find that the longest chain $l$ is in $\Theta(n)$. This result is proven in [1].

[1]: Albert, Michael H., and Alan M. Frieze. "Random graph orders." Order 6.1 (1989): 19-30.

(This is for additional knowledge) It is possible that assigning identifiers on the input graph such that the complexity of this MIS algorithm is minimized (that is, minimize $l$). The problem is NP-Hard as it is reducible to minimum coloring. This NP-Hard problem was given in: [2] and [3].

[2]: Deming, R. W. "Acyclic orientations of a graph and chromatic and independence numbers." Journal of Combinatorial Theory, Series B 26.1 (1979): 101-110.

[3]: Chvátal, Vašek, and Carsten Thomassen. "Distances in orientations of graphs." Journal of Combinatorial Theory, Series B 24.1 (1978): 61-75.

(Ok this is just for fun, and you can skip it) Now assume that you want to measure time with a different metric. And let's add a restriction to the definition of communication rounds (found in [4]). And let's say that a node 1) can send a message to only neighbor in a communication round, and 2) can receive a messages (more than one) from all its neighbors In such case, the order that a node follow to send a message to its neighbors will affect the time complexity. Let's consider three strategies that a node $v$ follows to visit its neighbors (with smaller identifiers) which are $\{u _1, ..., u _k\}$ such that $u _i \succ u _j$ if $i > j$. Then:

• Strategy 1: $v$ sends messages in an order from $u _k$, to $u _{k-1}$ ..., $u _1$ etc .. . This strategy leads to $\Theta(n)$ time complexity.

• Strategy 2: $v$ sends messages in an order from $u _1$, to $u _{2}$ ..., $u _k$ etc .. . This strategy leads to $\Theta(n^2)$ time complexity.

• Strategy 3: $v$ sends messages to its neighbors in a uniformly random order. This strategy will also lead to $\Theta(n^2)$ in expectation.

(Why I am interested in all that ?) - because it was found in some practical wireless networks (Bluetooth networks), that this slow MIS algorithm is the fastest although not being the theoretically fastest one. It was found that this type of networks follow the modified communication model I defined above.

[4]: Peleg, David. Distributed computing: a locality-sensitive approach. Vol. 5. Society for Industrial Mathematics, 1987.

-
Good call. The OP argues on an directed graph, but drew an undirected one, misleading the commenters. – Raphael Feb 3 '13 at 10:08
@Raphael I dont understand what you are saying. – AJed Feb 3 '13 at 20:39