MIS Algorithm: From Biological Inspiration to Computation

Maximal Independent Set (MIS): From Biology to Computation

Presenters: Leen Hassan, Yaman Dahle

Presentation Roadmap

1. Define the MIS Problem (Why it matters)<br>2. Explore the Biological Inspiration<br>3. Present the Formal Algorithm<br>4. Prove Correctness via Lemmas<br>5. Analyze Complexity & Conclude

Define the MIS Problem

Explore Biological Inspiration

Present the Formal Algorithm

Prove Correctness (Lemmas)

Analyze Complexity

Why MIS Matters?

• It creates a 'backbone' for wireless networks.<br>• Essential for efficient message routing.<br>• Allows clustering: selecting local leaders without a central authority.<br>• Vital for scalable ad-hoc sensor networks.

Informal Problem Definition

<b>The Setting: A Distributed System</b><br> • Processors solve a task jointly without global knowledge.<br> • Communication is strictly local (immediate neighbors only).<br><br> <b>The Goal: A Maximal Independent Set (MIS)</b><br> Select a subset of processors such that:<br> 1. <b>Independence:</b> No two neighboring processors are selected.<br> 2. <b>Dominance:</b> Every processor is either selected or adjacent to a selected one.

Formal Definition of MIS

Given a Graph G = (V, E), a subset A ⊆ V is a Maximal Independent Set if:<br><br>1. ∀ u, v ∈ A, (u, v) ∉ E<br> (No two nodes in A are neighbors)<br><br>2. ∀ v ∉ A, ∃ u ∈ A s.t. (u, v) ∈ E<br> (Every node outside A has a neighbor in A)

The Greedy Algorithm Approach

• Standard sequential method: Pick a node, remove its neighbors, repeat.<br>• <b>Problem:</b> In a distributed system, we don't have global vision.<br>• We need a parallel solution where nodes decide locally.

1. <b>Pick</b> an arbitrary node.<br>2. <b>Add</b> it to the Independent Set.<br>3. <b>Remove</b> it and all its neighbors.<br>4. <b>Repeat</b> until the graph is empty.

In a <b>distributed system</b>, we lack global knowledge.<br>Nodes cannot see the whole graph to "pick" sequentially.<br>We need a <b>local, parallel</b> strategy.

Luby’s Algorithm (1986)

• Each node chooses a random priority.<br>• A node joins the MIS if its priority is higher than all its neighbors’.<br>• All neighbors of a selected node become inactive.<br>• Repeat on the remaining nodes.

• <b>Randomness breaks symmetry.</b><br>• Terminates in O(log n) rounds with high probability.<br>• Correct and efficient in distributed networks.

Why is Distributed MIS Hard?

It requires <b>Symmetry Breaking</b>.<br><br>If all identical nodes try to become leaders at the same time, they collide.<br><br>If they wait for each other, it becomes too slow.<br><br>They must decide randomly, but efficiently.

The Challenge: Symmetry Breaking

<li style="margin-bottom: 15px;">In a distributed system, identical nodes lack a central coordinator.</li><li style="margin-bottom: 15px;">If they all act at once, they <b>collide</b>. If they all wait, they <b>deadlock</b>.</li><li style="margin-bottom: 15px;">They cannot simply "take turns" without communication.</li>

The Solution: Randomization

<li style="margin-bottom: 15px;">Nodes determine their actions by flipping a coin.</li><li style="margin-bottom: 15px;">Randomization breaks the symmetry naturally.</li><li style="margin-bottom: 15px;">It allows fast local decisions without global coordination.</li>

The Biological Problem: SOP Selection

<li style="margin-bottom: 20px;"><b>The Context:</b> During the development of the fly, groups of identical cells must decide which will become sensory organs (SOPs).</li><li style="margin-bottom: 20px;"><b>The Dilemma:</b> Any cell can be a leader, but neighboring cells cannot both be selected. There is no central controller.</li><li style="margin-bottom: 20px;"><b>The Mechanism:</b> "Lateral Inhibition" — Each cell communicates only with its neighbors.</li><li style="margin-bottom: 20px;"><b>The Rule:</b> Once a cell is selected, it inhibits all its neighbors.</li><li style="margin-bottom: 20px;"><b>The Result:</b> An exact MIS pattern emerges naturally.</li>

Why Luby’s Algorithm Cannot Be Implemented by the Fly

➡️ Biological systems have much weaker communication capabilities

How Symmetry Is Broken in the Fly

<ul style='list-style-type: disc; padding-left: 40px;'> <li style='margin-bottom: 30px;'>All cells start in the same state</li> <li style='margin-bottom: 30px;'>Cells gradually increase their tendency to become SOP</li> <li style='margin-bottom: 30px;'>Small random differences appear between neighboring cells</li> <li style='margin-bottom: 30px;'>A cell that becomes slightly ahead inhibits its neighbors</li> <li style='margin-bottom: 30px;'>Inhibition amplifies this difference and prevents neighbors from catching up</li> <li style='margin-bottom: 30px; font-weight:bold; color:#1e40af;'>Outcome: A single SOP is selected from a symmetric group.</li> </ul>

From Biology to Algorithm

We translate the biological mechanism into computer science terms:

<table style='width:100%; border-collapse:collapse; font-size:45px; margin-top:40px;'> <tr style='background-color:#34495e; color:white;'><th style='padding:20px; text-align:left;'>Biological Element</th><th style='padding:20px; text-align:left;'>Computational Equivalent</th></tr> <tr style='background-color:#ecf0f1;'><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>Cell</td><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>Processor / Node</td></tr> <tr style='background-color:#ffffff;'><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>Delta Protein</td><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>1-bit Message</td></tr> <tr style='background-color:#ecf0f1;'><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>Lateral Inhibition</td><td style='padding:20px; border-bottom:2px solid #bdc3c7;'>Node becomes Inactive</td></tr> <tr style='background-color:#ffffff;'><td style='padding:20px;'>SOP Selection</td><td style='padding:20px;'>Joining the MIS</td></tr> </table>

The Rate Change Model

<div style="margin-bottom: 40px;"> <strong>Traditional Problem:</strong><br> Traditional algorithms need to know the number of neighbors (degree). <span style="color:#C62828;">Cells don't know their degree.</span> </div> <div style="padding-left: 20px; border-left: 6px solid #1565C0;"> <strong style="color:#1565C0; display:block; margin-bottom:15px;">Biological Solution:</strong> <ul style="list-style-type: none; padding: 0; margin: 0;"> <li style="margin-bottom: 20px; display:flex; align-items:start;"><span style="color:#1565C0; margin-right:15px; font-size:40px;">•</span> Start with a very low probability of speaking up.</li> <li style="margin-bottom: 20px; display:flex; align-items:start;"><span style="color:#1565C0; margin-right:15px; font-size:40px;">•</span> Gradually increase the probability over time.</li> <li style="margin-bottom: 0px; display:flex; align-items:start;"><span style="color:#1565C0; margin-right:15px; font-size:40px;">•</span> This avoids an initial 'shouting match' (collisions).</li> </ul> </div>

The Algorithm in Action

Nodes broadcast randomly. If they speak alone, they join MIS (Blue). Their neighbors hear them and exit (Gray).

<ul style="list-style: none; padding: 0;"> <li style="margin-bottom: 50px;"> <strong style="color: #0e2a47; font-size: 55px; display: block; margin-bottom: 15px;">1. Try</strong> <span style="color:#333; font-size: 45px;">Each node randomly decides whether to propose itself as a leader.</span> </li> <li style="margin-bottom: 50px;"> <strong style="color: #0e2a47; font-size: 55px; display: block; margin-bottom: 15px;">2. Listen</strong> <span style="color:#333; font-size: 45px;">The node checks its neighbors: "Did anyone else propose?"</span> </li> <li style="margin-bottom: 50px;"> <strong style="color: #0e2a47; font-size: 55px; display: block; margin-bottom: 15px;">3. Decide</strong> <span style="color:#333; font-size: 45px;">If the node is the sole volunteer (or wins the tie-break), it joins the independent set.</span> </li> </ul>

Table 1. MIS Algorithm

1. Algorithm: MIS (n, D) at node u 2. For i = 0: log D 3. For j = 0: M log n // M is constant derived below 4. * exchange 1* 5. v = 0 6. With probability 1/2^(log D - i) broadcast B to neighbors and set v = 1 7. If received message from neighbor, then v = 0 8. * exchange 2 * 9. If v = 1 then 10. Broadcast B; join MIS; exit the algorithm 11. Else 12. If received message B in this exchange, then mark node u inactive; exit 13. End 14. End 15. End

Proof of Lemma 1

<b>Lemma 1:</b> No two nodes in A are connected to each other.

<b>Proof:</b> Node w joins set A if it broadcast at an exchange of type 1 and none of its neighbors broadcasts at the same exchange. This means that none of its neighbors has joined A in a previous step since when a node joins A all its neighbors are marked inactive in the exchange in which it joins A. Thus two neighboring nodes cannot join A at the same exchange, and when the earlier of them joins, the other one is marked inactive and will never join A. ■

<b>Lemma 1.</b><br>No two nodes in <b>A</b> (the output set) are connected to each other.

<div style="margin-left: 20px;"> <div style="margin-bottom:20px; font-weight:bold; color:#000000;">Proof:</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0;"> <li style="margin-bottom:15px; color:#000000;">A node <b>w</b> joins set <b>A</b> only if: <ul style="list-style-type: circle; padding-left: 50px; margin-top:10px; color:#222222;"> <li>It broadcasts in Exchange 1, and</li> <li>None of its neighbors broadcast in the same exchange.</li> </ul> </li> <li style="margin-bottom:15px; color:#000000;">When a node joins <b>A</b>: <ul style="list-style-type: circle; padding-left: 50px; margin-top:10px; color:#222222;"> <li>All its neighbors are immediately marked inactive.</li> </ul> </li> <li style="margin-bottom:15px; color:#000000;">Therefore: <ul style="list-style-type: circle; padding-left: 50px; margin-top:10px; color:#222222;"> <li>Two neighbors cannot join <b>A</b> in the same exchange.</li> <li>If one joins earlier, the other becomes inactive.</li> </ul> </li> </ul> <div style="margin-top:40px; border-top: 3px solid #000000; padding-top:20px; font-weight:bold; color:#000000;"> Conclusion: No two neighboring nodes can both belong to <b>A</b>. ∎ </div> </div>

Lemma 2 (Maximality)

<b>Lemma 2:</b> If node w exits the algorithm and it did not join A, then it is connected to a node in A.

<b>Proof:</b> This can only happen if node w executes the "then" part in Line 12 of the code.<br>This occurs only upon receiving a message from a neighboring node that has just joined A. ■

<b>Lemma 2.</b><br>If node w exits the algorithm and it did not join A, then it is connected to a node in A.

<div style="margin-left: 20px;"> <div style="margin-bottom:20px; font-weight:bold; color:#000000;">Proof:</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0;"> <li style="margin-bottom:30px; color:#000000;">A node exits the algorithm only if: <ul style="list-style-type: circle; padding-left: 50px; margin-top:15px; color:#222222;"> <li>It joins the MIS, or</li> <li>It receives a broadcast from a neighbor and becomes inactive.</li> </ul> </li> <li style="margin-bottom:30px; color:#000000;">In the latter case (inactive): <ul style="list-style-type: circle; padding-left: 50px; margin-top:15px; color:#222222;"> <li>The broadcasting neighbor definitely joins the MIS.</li> </ul> </li> </ul> <div style="margin-top:50px; border-top: 3px solid #000000; padding-top:30px; font-weight:bold; color:#000000;"> Conclusion: Every node not in the MIS is adjacent to a node in the MIS. ∎ </div> </div>

Lemma 3 (Efficiency)

<b>Lemma 3:</b> If w is in A then all the neighbors of w become inactive.

<b>Proof:</b> By lemma 1 we know that none of w's neighbors is in A. By the code (exchange 2) when w joins A it broadcasts to all its neighbors that then become inactive and exit the algorithm (Line 12). ■

<b>Lemma 3:</b><br>If node w is in A, then all neighbors of w become inactive.

<div style="margin-left: 20px;"> <div style="margin-bottom:20px; font-weight:bold; color:#000000;">Proof:</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0;"> <li style="margin-bottom:30px; color:#000000;">By <b>Lemma 1</b>, we know that none of w's neighbors are in A.</li> <li style="margin-bottom:30px; color:#000000;">By the code (Exchange 2), when w joins A: <ul style="list-style-type: circle; padding-left: 50px; margin-top:15px; color:#222222;"> <li>It broadcasts to all its neighbors.</li> <li>These neighbors then become inactive and exit.</li> </ul> </li> </ul> <div style="margin-top:50px; border-top: 3px solid #000000; padding-top:30px; font-weight:bold; color:#000000;"> Conclusion: w eliminates all its neighbors. ∎ </div> </div>

<ul style="margin:0; padding-left:40px; list-style-type: disc;"> <li style="margin-bottom:20px;">By <b>Lemma 1</b>, we know that none of <b>w</b>'s neighbors are in <b>A</b>.</li> <li style="margin-bottom:20px;">By the code (Exchange 2), when <b>w</b> joins <b>A</b>, it broadcasts to all its neighbors.</li> <li>Consequently, these neighbors become inactive and exit the algorithm. ■</li> </ul>

Lemma 4 (Degree Reduction Lemma)

<b>Lemma 4:</b> With probability at least (1 - i/n²) there are no nodes with degree > D/2^i at the end of phase i.

<b>Proof Overview:</b> By induction on i. Base i=0 is trivial. For the step, assume correctness for i-1. In phase i, the broadcast probability is tuned such that nodes with high degree are very likely to be removed (either joining A or neighbors joining A). This leads to a low probability of collision and high probability of degree reduction. (See supplementary material p.16 for full inductive math). ■

<b>Lemma 4.</b><br>With probability at least 1 − i/n², by the end of phase i, there are no nodes with degree greater than D/2ⁱ.

<div style="margin-left: 20px;"> <div style="margin-bottom:20px; font-weight:bold; color:#000000;">Proof (Induction on i):</div> <div style="margin-bottom:15px; font-weight:bold; color:#000000; text-decoration: underline;">Base Case (i = 0)</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0; margin-bottom:20px;"> <li style="color:#000000;">For i = 0, the claim holds trivially, since D is an upper bound on the number of neighbors of any node.</li> </ul> <div style="margin-bottom:15px; font-weight:bold; color:#000000; text-decoration: underline;">Induction Hypothesis</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0;"> <li style="color:#000000;">Assume that by the end of phase i − 1, with probability at least 1 − (i−1)/n², there are no nodes with more than 2D/2ⁱ active neighbors.</li> </ul> </div>

Lemma 4: Induction Step

<div style="margin-left: 20px; font-size: 42px; line-height: 1.6;"> <ul style="list-style-type: disc; padding-left: 50px; margin:0;"> <li style="margin-bottom:35px; color:#000000;">If no nodes have degree > D/2ⁱ at start of phase i, claim holds.</li> <li style="margin-bottom:35px; color:#000000;">Otherwise, let v be a node with degree > D/2ⁱ.</li> <li style="margin-bottom:35px; color:#000000;">During phase i, broadcast probability is p = 1/(D/2ⁱ).</li> </ul> <div style="margin-top:40px; font-weight:bold; color:#000000; margin-bottom:20px;">Probability of a Broadcast</div> <ul style="list-style-type: circle; padding-left: 50px; margin:0; margin-bottom:35px;"> <li style="color:#222; margin-bottom:15px;">Prob(v or neighbors broadcast) ≥ 1 − 1/e.</li> </ul> <div style="font-weight:bold; color:#000000; margin-bottom:20px;">Collision-Free Broadcast</div> <ul style="list-style-type: circle; padding-left: 50px; margin:0; margin-bottom:35px;"> <li style="color:#222; margin-bottom:15px;">Max neighbors is 2D/2ⁱ (by Hypothesis).</li> <li style="color:#222;">Thus, probability of no collision is bounded by a constant.</li> </ul> <div style="border-top: 3px solid #000; padding-top:20px; margin-top:30px; font-weight:bold;"> Therefore, in each step, v has a constant probability of being removed. </div> </div>

Lemma 4: Conclusion

<div style="margin-left: 20px; font-size: 42px; line-height: 1.6;"> <div style="font-weight:bold; color:#000000; margin-bottom:20px;">Multiple Steps in a Phase</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0; margin-bottom:40px;"> <li style="margin-bottom:35px; color:#000000;">Phase i consists of M log n steps.</li> <li style="margin-bottom:35px; color:#000000;">Probability that node v is not removed is at most:<br> (1 − c)^{M log n} ≤ 1/n²</li> </ul> <div style="font-weight:bold; color:#000000; margin-bottom:20px;">Union Bound</div> <ul style="list-style-type: disc; padding-left: 50px; margin:0; margin-bottom:40px;"> <li style="margin-bottom:35px; color:#000000;">There are at most n nodes with degree > D/2ⁱ.</li> <li style="margin-bottom:35px; color:#000000;">By a union bound, the probability that any such node remains is at most 1/n².</li> </ul> <div style="margin-top:40px; border-top: 3px solid #000000; padding-top:30px; font-weight:bold; color:#000000;"> Thus, with probability at least 1 − i/n², there are no nodes with degree greater than D/2ⁱ at the end of phase i. ∎ </div> </div>

Theorem (Main Result)

<b>Theorem 1:</b> With probability 1 - (log D)/n², all nodes are either in A or connected to a node in A by the end of the algorithm.

Using Lemma 4, by the end of phase log D, remaining nodes have degree of 0 relative to active nodes (they have no active neighbors). These nodes will join A with no collisions. Lemma 3 ensures they have no neighbors already in A. Thus, a valid MIS is formed.

With high probability, the distributed algorithm outputs a Maximal Independent Set (MIS).

<div style='font-weight:bold; margin-bottom:30px; color:#000000;'>Moreover:</div> <ul style='list-style:none; padding:0; margin:0;'> <li style='margin-bottom:30px; padding-left: 40px; position: relative;'> <span style='position: absolute; left: 0; color: #0047AB; font-weight: bold;'>•</span> Runs in <strong>polylogarithmic time</strong> </li> <li style='margin-bottom:30px; padding-left: 40px; position: relative;'> <span style='position: absolute; left: 0; color: #0047AB; font-weight: bold;'>•</span> Uses only <strong>local communication</strong> </li> <li style='margin-bottom:30px; padding-left: 40px; position: relative;'> <span style='position: absolute; left: 0; color: #0047AB; font-weight: bold;'>•</span> Requires <strong>no global knowledge</strong> of the network </li> </ul>

Complexity Analysis

<b>Time Complexity:</b><br>O(log D · log n). Since D ≤ n, it is O(log² n).<br><br><b>Message Complexity:</b><br>Expected number of messages is linear in the number of nodes (O(n)).<br>This is optimal.<br>Messages are only 1-bit (Beep).

⏱️ Time Complexity

<ul style="margin:0; padding-left:40px; list-style-type:disc;"> <li style="margin-bottom:15px;">Algorithm runs in <b>O(log² n)</b> rounds</li> <li style="margin-bottom:15px;">There are <b>O(log D)</b> phases</li> <li style="margin-bottom:15px;">Each phase has <b>O(log n)</b> steps</li> </ul> <div style="margin-top:25px; font-weight:bold; color:#0056b3;"> ➡️ Total: O(log D · log n) = O(log² n) </div>

📩 Message Complexity

<ul style="margin:0; padding-left:40px; list-style-type:disc;"> <li style="margin-bottom:15px;">Sends <b>constant-size messages</b> (1 bit)</li> <li style="margin-bottom:15px;">Messages sent <b>only to neighbors</b></li> <li>Total complexity is <b>polylogarithmic</b> per node</li> </ul>

Summary

Following the nature of the fruit fly, we derived an efficient algorithm for the MIS problem.<br><br>• No need to know neighbor count.<br>• Minimal communication (1-bit).<br>• Optimal Message Complexity.<br>• Demonstrated similarity between Biological and Computational efficiency.

MIS is a fundamental coordination problem

Deterministic solutions fail (symmetry)

Biology inspires a probabilistic algorithm

Algorithm is correct, fast, and scalable

Local randomness can replace global control.

Thank You

Any Questions?