Biological Algorithms: Bio-Inspired Maximal Independent Set

Learn how fruit fly sensory organ development inspires efficient distributed computing algorithms for sensor networks and swarm robotics.

#bio-inspired-algorithms#distributed-computing#mis-algorithm#computer-science#biomimicry#sensor-networks#robotics

Watch
Pitch

Maximal Independent Set

A Biological Solution to a Distributed Computing Problem

Yaman Dahle, Leen Hassan

Made by

Why MIS Matters?

It helps systems work without one boss

In real systems (Wi-Fi networks, sensors, traffic systems), there is no central controller. MIS lets the system organize itself and choose leaders automatically.

It avoids interference and chaos

MIS makes sure important units (like routers or controllers) are not too close to each other, which prevents conflicts, noise, or interference, while still covering everyone.

Made by

Informal Problem Definition

We consider a distributed system in which processors jointly solve a task, without any processor receiving all the inputs or observing all the outputs.

Each processor communicates only with its immediate neighbors, and has no global knowledge of the system.

The Goal: Select a subset of processors such that:

No two neighboring processors are selected.
Every processor is either selected or adjacent to a selected one.

Made by

MIS: Maximal Independent Set

We are given a network (graph) of nodes and connections.
We need to find a set of nodes A such that:

IndependenceNo two nodes in A are directly connected (A is an independent set).

MaximalityEvery node in the network is either in A or directly connected to a node in A (A is maximal).

This set A is called a Maximal Independent Set (MIS).

Made by

The "Greedy" Algorithm (Centralized)

The obvious way if you have a "Boss".

How it works:

Pick a node -> Add to Set A.
Remove its neighbors.
Repeat until graph is empty.

The Problem: It is Sequential (needs a central coordinator/Boss).
We need a Parallel solution (No Boss).

Sequential = Slow & Centralized

Made by

The Challenge: Symmetry Breaking

The Scenario:
Imagine all nodes in the network are identical. They run the exact same code and wake up at the exact same time.

The Conflict:
If Node A decides "I'll join the set!", its neighbor Node B (running the same logic) does the exact same thing.

Result: Deterministic decisions lead to conflicts or no progress.

The Solution:
Introduce randomness so nodes can make different decisions and break symmetry.

Made by

The Biological Coordination Problem

During the development of the fly, groups of identical cells must decide which will become sensory organs (SOPs).

The Dilemma: Any cell can be a leader, but neighboring cells cannot both be selected.

There is no central controller. Each cell communicates only with its neighbors to create this perfect pattern.

Abstract schematic diagram of a biological cell grid. A pattern of hexagonal cells packed together like a honeycomb. Some cells are highlighted in bright electric blue (leaders), surrounded by plain white cells. CRITICAL: The blue cells are spaced out perfectly—NO two blue cells touch each other. Every blue cell is completely surrounded by white cells. Clean, minimalist vector art style, high contrast, easy to understand.

Made by

How Symmetry Is Broken in the Fly

All cells start in the same state

Cells gradually increase their tendency to become SOP

Small random differences appear between neighboring cells

A cell that becomes slightly ahead inhibits its neighbors

Inhibition amplifies this difference and prevents neighbors from catching up

Outcome: A single SOP is selected from a symmetric group.

Minimalist diagram of 'symmetry breaking' in biology. Two identical circles side-by-side. Step 1: Both equal size, gray. Step 2: One circle grows slightly larger and turns blue, while the other shrinks slightly. Step 3: The blue circle is large and dominant (Leader), the other is small and gray (Inhibited). Simple vector style, white background, clean lines.

From random noise to perfect order

Made by

From Biology to Algorithm

How we translate the fly's method into code:

Nodes behave like cells
Decisions are probabilistic, not deterministic
Small randomness breaks symmetry
Local inhibition ↔ neighbors cannot both join MIS

Key Message: The algorithm mimics the biological process.

Made by

The Key Insight: Rate Change

Traditional algorithms need to know the number of neighbors (degree). Cells don't know their degree.

Biological Solution:
Start with a very low probability of speaking up.
Gradually increase the probability over time.
This avoids an initial 'shouting match' (collisions).

Chart

Made by

Algorithm in Action

The 3-Step Cycle:

1. Broadcast (Red):
Center node wakes up and yells "BEEP!"
2. Inhibit (Yellow):
Now 8 neighbors hear the beep and must stay "Quiet".
3. Parallel Leaders:
Distant nodes can become LEADERS simultaneously.
This is how it scales!

Made by

Algorithm Parameters

Key variables definitions

n – number of nodes in the network
D – maximum degree (max number of neighbors)
M – a fixed constant (from analysis, not important now)
exchange – one communication round with neighbors
B – one-bit message

Made by

MIS Algorithm

REPORTS
Algorithm: MIS (n, D) at node u
For i = 0 : logD
  For j = 0 : M log n   // M is constant derived below
    * exchange 1 *
    v = 0
    With probability 1 / (2^(logD - i)) broadcast B to neighbors and set v = 1
    If received message from neighbor, then v = 0
    * exchange 2 *
    If v = 1 then
     Broadcast B; join MIS; exit the algorithm
   Else
     If received message B in this exchange, then mark node u inactive; exit the algorithm
   End
 End
End

Rules

● Nodes run this code in parallel

● Communication is only local

Made by

Lemma 1: Independence

Scenario 1: Success

Broadcast!

—

W broadcasts.
V is silent.
W joins Set A.

Scenario 2: Conflict

Broadcast!

—

Broadcast!

Both broadcast.
They hear each other.
Neither joins Set A.

No two nodes in the Independent Set (A) are connected.

A node only joins A if it broadcasts and hears nothing. If two neighbors transmit, they block each other. If one joins earlier, the neighbor becomes inactive immediately. Thus, neighbors can never join together.

Made by

Lemmas 2 & 3: Exiting the Algorithm

Lemma 2: The Only Way Out

If a node leaves and ISN'T in A...

Exits ❌

⬅ connected to ➡

Joined A ✅

Proof: W only executes the "exit" code if it receives a message from a neighbor who joined A.

Lemma 3: Cleaning Up

If W joins A...

Joined A

🌊 signal ➡

All

Become Inactive

Proof: When W joins, it broadcasts. Neighbors receive this, become inactive, and exit.

What does this mean?

Together, these lemmas prove that nodes don't disappear randomly.
They are either Selected (Joined A) or Removed by a neighbor.
The graph essentially "crumbles" around the selected nodes.

Made by

Lemma 4: Degree Reduction

Phase 0: Degree ≤ D

⬇

Phase 1: Degree ≤ D/2

⬇

Phase 2: Degree ≤ D/4

⬇

Phase i: Degree ≤ D/2ⁱ

The Logic (Proof Sketch)

1. The Hypothesis

Assume by phase i-1, max degree has effectively halved.

2. The Action

In Phase i, we run M log n steps. Probability of speaking is tuned to 1/degree.

3. The Cleansing

High-degree nodes (or their neighbors) are very likely to speak up eventually.
Once they speak, they are removed (Join or Inactive).

Result: With high probability, any node that still has "too many" neighbors will be eliminated.

Statement: With probability ≥ 1 - i/n², max degree ≤ D/2ⁱ

Made by

What makes this special?

Standard Algorithms

❌ Must know "N" (Total nodes)
❌ Must know "Delta" (Max neighbors)
❌ Complex IDs (Node #1345)
❌ Heavy logic

Fly Algorithm

✅ Zero Knowledge required
✅ Doesn't count neighbors
✅ No IDs (Anonymous)
✅ Only 1 bit of memory!

Made by

Comparison: Bandwidth

How much data needs to be sent?

Standard: Log(N) bits

"I am Node #12,405"

Fly Algorithm: 1 bit

"BEEP!"

Conceptual illustration comparing a heavy data packet (like a mail package) vs a simple light signal (like a flash of light), minimalist vector art

Made by

Robustness: Handling Failure

The "Crash" Scenario

In complex algorithms, if a node crashes during the election, the whole system might freeze or need a restart.

The Biological Way

Biological systems are messy. Cells die. The algorithm handles this naturally:

If a Leader dies → The neighbors stop receiving 'Inhibit' → They wake up and elect a NEW leader.

Diagram showing a network self-healing, broken node being bypassed or replaced by neighbors, digital abstract art, blue and green tones

Made by

Application 1: Sensor Networks

Imagine dropping 10,000 sensors into a forest to detect fire.

They have tiny batteries and cannot be recharged.

Why the Fly Algorithm?

🔋 Energy Efficient: 1-bit messages mean longer life.
⚡ Fast Setup: Networks organize in seconds (Microseconds).
🛡️ Resilient: If sensors fail (fire, damage), the network adapts instantly.

Made by

Swarm of futuristic drones flying in formation with glowing lights, cinematic sci-fi style, dark sky background

Application 2: Swarm Robotics

Decentralized Control

Drones cannot always talk to a base station. They must decide among themselves who leads the formation.

Dynamic Environment

As drones move, connections change. The Fly Algorithm doesn't need a static map—it works on the fly (literally).

Made by

The Future: Algorithms in Nature

🐜

Ants

Shortest path finding (TSP). Optimized routing for internet traffic.

🐝

Bees

Decision making and resource allocation. Server load balancing.

🪰

Flies

MIS Selection. The algorithm we studied today.

"Biology has 3 billion years of R&D."

Made by

Limitations & Considerations

Probabilistic Nature

It is not 100% deterministic. There is a tiny error probability (Las Vegas algorithm), though it approaches zero as time goes on.

Synchronization

The basic model assumes nodes have a common clock (Rounds). Asynchronous versions are harder to implement in biology.

Energy vs Speed

While message size is small (1 bit), the number of rounds is logarithmic. For extremely small graphs, a simpler approach might be faster.

Made by

Summary

We started with a fly's brain and ended with a state-of-the-art computer algorithm.

1. Biological Inspiration: SOP Bristles need spacing.
2. The Algorithm: Stochastic feedback (Beep & Listen).
3. Efficiency: O(log n) time using only 1-bit messages.
4. Application: Ideal for resource-constrained networks.

Made by

"Simplicity is the ultimate sophistication."

The fruit fly teaches us that we don't need complex hardware to solve difficult problems. We just need smarter collaboration.

Made by

References

[1] Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., & Levy, Z. (2011). A Biological Solution to a Fundamental Distributed Computing Problem. Science.
[2] Luby, M. (1986). A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing.
[3] Lynch, N. A. (1996). Distributed Algorithms. Morgan Kaufmann.

Made by

Q & A

Thank You!

Made by

DESIGNER-MADE
PRESENTATION,
GENERATED FROM
YOUR PROMPT

Create your own professional slide deck with real images, data charts, and unique design in under a minute.

Generate For Free

Biological Algorithms: Bio-Inspired Maximal Independent Set

Learn how fruit fly sensory organ development inspires efficient distributed computing algorithms for sensor networks and swarm robotics.

Maximal Independent Set

A Biological Solution to a Distributed Computing Problem

Yaman Dahle, Leen Hassan

Why MIS Matters?

<div style="margin-bottom:40px; border-left: 5px solid #4fd1c5; padding-left: 20px;">1. It works without one bossIn real systems (Wi-Fi, sensors), there is no central controller. MIS lets the system organize itself and choose leaders automatically.</div><div style="border-left: 5px solid #fc8181; padding-left: 20px;">2. It avoids interferenceIt makes sure important units (like routers) are not too close. This prevents conflicts and signal noise, whilst still covering everyone.</div>

It helps systems work without one boss

In real systems (Wi-Fi networks, sensors, traffic systems), there is no central controller. MIS lets the system organize itself and choose leaders automatically.

It avoids interference and chaos

MIS makes sure important units (like routers or controllers) are not too close to each other, which prevents conflicts, noise, or interference, while still covering everyone.

Informal Problem Definition

We consider a distributed system in which processors jointly solve a task, without any processor receiving all the inputs or observing all the outputs.Each processor communicates only with its immediate neighbors, and has no global knowledge of the system.

The Goal: Select a subset of processors such that:<ul style="font-size:1.3em; line-height:1.5; color: #4a5568; margin:0; padding-left:25px;"><li>No two neighboring processors are selected.</li><li>Every processor is either selected or adjacent to a selected one.</li></ul>

MIS: Maximal Independent Set

<ul style="list-style:none; padding:0;"><li style="margin-bottom:25px; font-size:1.1em;">🎯 Goal: Elect a set of local leaders in a network.</li><li style="margin-bottom:25px; color:#5fa6d5;">1. Independence: No two leaders can be connected (neighbors).</li><li style="color:#84b082;">2. Dominance: Every non-leader must be connected to at least one leader.</li></ul>

We are given a network (graph) of nodes and connections. We need to find a set of nodes A such that:

IndependenceNo two nodes in A are directly connected (A is an independent set).

MaximalityEvery node in the network is either in A or directly connected to a node in A (A is maximal).

This set A is called a Maximal Independent Set (MIS).

The "Greedy" Algorithm (Centralized)

<ol><li>Gather the entire graph topology in one central processor.</li><li>Select an arbitrary node v to join the MIS.</li><li>Remove v and all its neighbors from the graph.</li><li>Repeat until the graph is empty.</li></ol>

Major Drawback: Requires global knowledge. In massive networks (sensors, biology), no single node knows the whole specific topology.

<ol style="margin:0; padding-left:30px;"> <li style="margin-bottom:10px;">Pick a node -> Add to Set A.</li> <li style="margin-bottom:10px;">Remove its neighbors.</li> <li>Repeat until graph is empty.</li> </ol>

The Problem: It is Sequential (needs a central coordinator/Boss). We need a Parallel solution (No Boss).

The Challenge: Symmetry Breaking

The Scenario: Imagine all nodes in the network are identical. They run the exact same code and wake up at the exact same time. The Conflict: If Node A decides "I'll join the set!", its neighbor Node B (running the same logic) does the exact same thing. Result: Deterministic decisions lead to conflicts or no progress. The Solution: Introduce randomness so nodes can make different decisions and break symmetry.

The Biological Coordination Problem

<div style="font-size: 44px; line-height: 1.4; color: #37474f;"> During the development of the fly, groups of identical cells must decide which will become sensory organs (SOPs). The Dilemma: Any cell can be a leader, but neighboring cells cannot both be selected. There is no central controller. Each cell communicates only with its neighbors to create this perfect pattern. </div>

How Symmetry Is Broken in the Fly

Delta-Notch Signaling: • A cell produces a protein called Delta. • Delta binds to Notch receptors on neighbors. • Effect: "If I am active (Delta), you stay quiet (Inhibited)." • This is a 1-bit communication channel.

<div style="font-size: 38px; line-height: 1.4; color: #37474f;"> How do identical cells break the tie? <ul style="list-style: none; padding: 0;"> <li style="margin-bottom: 25px; border-left: 6px solid #009688; padding-left: 20px;"> Feedback Loop: Ideally, cells compete. If one gets slightly ahead, it suppresses its neighbors. </li> <li style="margin-bottom: 25px; border-left: 6px solid #009688; padding-left: 20px;"> The Signal: "I am becoming a Leader (SOP), so you must stay as normal skin!" </li> <li style="border-left: 6px solid #009688; padding-left: 20px;"> The Result: A specialized cell surrounded by non-specialized ones. </li> </ul> </div>

<div style="font-size:0.9em;"> All cells start in the same state Cells gradually increase their tendency to become SOP Small random differences appear between neighboring cells A cell that becomes slightly ahead inhibits its neighbors Inhibition amplifies this difference and prevents neighbors from catching up <div style="margin-top:30px; background:#e8f4fd; padding:20px; border-radius:15px; color:#2c3e50; font-weight:600;"> Outcome: A single SOP is selected from a symmetric group. </div> </div>

From random noise to perfect order

From Biology to Algorithm

<div style="width:100%; max-width:1400px; margin:0 auto;"> How we translate the fly's method into code: <ul style="list-style:none; padding:0;"> <li style="margin-bottom:30px; border-left:8px solid #3498db; padding-left:30px;"> Nodes behave like cells </li> <li style="margin-bottom:30px; border-left:8px solid #3498db; padding-left:30px;"> Decisions are probabilistic, not deterministic </li> <li style="margin-bottom:30px; border-left:8px solid #3498db; padding-left:30px;"> Small randomness breaks symmetry </li> <li style="margin-bottom:30px; border-left:8px solid #3498db; padding-left:30px;"> Local inhibition ↔ neighbors cannot both join MIS </li> </ul> <div style="margin-top:60px; background:#e8f6f3; padding:40px; border-radius:20px; color:#16a085; font-weight:600; border-left: 10px solid #1abc9c; text-align:center; box-shadow: 0 10px 30px rgba(0,0,0,0.05);"> Key Message: The algorithm mimics the biological process. </div> </div>

Mapping biological principles to computational rules

The Key Insight: Rate Change

Traditional algorithms need to know the number of neighbors (degree). Cells don't know their degree. Biological Solution: Start with a very low probability of speaking up. Gradually increase the probability over time. This avoids an initial 'shouting match' (collisions).

Algorithm in Action

The 3-Step Cycle:

1. Broadcast (Red): Center node wakes up and yells "BEEP!"

2. Inhibit (Yellow): Now 8 neighbors hear the beep and must stay "Quiet".

3. Parallel Leaders: Distant nodes can become LEADERS simultaneously. This is how it scales!

Algorithm in Action

[ Insert Video / Simulation Here ]\n\nShow nodes blinking,\nchecking neighbors,\nand turning Blue (Selected)

<div style="margin-bottom: 30px;">1. Wake Up Each node wakes up with probability p.</div><div style="margin-bottom: 30px;">2. Broadcast Send "I'm here!" to neighbors.</div><div style="margin-bottom: 30px;">3. Decide Silence? Join the set. Noise? Back off and try again.</div>

Video Placeholder: Simulation Demo

Algorithm Parameters

Key variables definitions

Rules

Executed by every node in parallel.

Nodes run this code in parallel

Communication is only local

// Algorithm for every Node v

Status = ACTIVE

WHILE (Status is ACTIVE):

1. Wake up with probability p

2. IF awake: Broadcast "BEEP" to neighbors

3. IF (Awake AND Heard no "BEEPs"):

-> Become LEADER (Exit)

4. ELSE IF (Heard a "BEEP" from neighbor):

-> Become FOLLOWER (Exit)

5. ELSE: Repeat next round

Table 1. MIS algorithm.

REPORTS 1. Algorithm: MIS (n, D) at node u 2. For i = 0 : logD 3. For j = 0 : M log n // M is constant derived below 4. * exchange 1 * 5. v = 0 6. With probability 1 / (2^(logD - 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 the algorithm 13. End 14. End 15. End

MIS Algorithm

Proof of Correctness (Safety)

Lemma 1: No two nodes in MIS are connected. Why? A node only joins the MIS if it broadcasts AND receives no message. If two neighbors both broadcast, they both receive a message, so neither joins. They block each other.

Lemma 2: If a node exits without joining MIS, it must have a leader neighbor. Why? You only exit if you receive a 'Join' message from a neighbor who became a leader.

Lemma 1: Independence

Lemma 1: Probability of Success

There is a constant probability that a node joins the MIS or a neighbor joins in each round.

Lemma 2: Edge Removal Rate

In each phase, a constant fraction of edges are removed from the graph with high probability.

Lemma 3: Runtime Complexity

The algorithm terminates in O(log n) rounds with high probability.

How do we guarantee progress? We need a node to speak ALONE. The algorithm adjusts the broadcast probability p to find the balance.

Everyone talks → Collision. No one hears clearly.

p = 1 / d (where d is neighbors). Constant probability of success!

No one talks → Silence. Nothing happens.

No two nodes in the Independent Set (A) are connected.

A node only joins A if it broadcasts and hears nothing. If two neighbors transmit, they block each other. If one joins earlier, the neighbor becomes inactive immediately. Thus, neighbors can never join together.

Proof of Efficiency (Runtime)

Lemma 4: By the end of phase i, there are no nodes with degree > D/2^i. Essentially, as the probability of shouting increases (doubles), high-degree nodes are very likely to be 'cleared out' (either join MIS or be inhibited).

Theorem 1: The algorithm finishes in O(log N) time. This matches the speed of the best known computer algorithms, but uses much simpler (biological) assumptions.

When a node joins the MIS, it and its neighbors retire. This means all the connections (edges) touching them are gone. Even if the graph is huge, it "crumbles" very fast.

Lemmas 2 & 3: Exiting the Algorithm

Summary & Impact

<ul><li>Biology solves computation: Flies solved distributed leader election millions of years ago.</li><li>Constraint efficiency: Limited information (no degree knowledge) and limited bandwidth (1-bit) can still yield optimal speed.</li><li>Application: Perfect for low-power Sensor Networks and nanoscale computing.</li></ul>

Because we remove a constant fraction of edges in every phase (Lemma 2), the size of the problem shrinks exponentially. Even with billions of nodes, it finishes in just a few dozen rounds.

Theorem 1: The algorithm terminates in O(log n) time with high probability.

Lemma 4: Degree Reduction

Because we remove a constant fraction of edges in every phase... The network collapses exponentially fast. This creates the O(log n) runtime.

Comparison: Knowledge vs Ignorance

Bandwidth Efficiency

Robustness

Application: WSN

Swarm Robotics

Nature Algorithms

Limitations

Summary

Conclusion

References

Q&A

bio-inspired-algorithms
distributed-computing
mis-algorithm
computer-science
biomimicry
sensor-networks
robotics

Maximal Independent Set

A Biological Solution to a Distributed Computing Problem

Why MIS Matters?

It helps systems work without one boss

It avoids interference and chaos

Informal Problem Definition

MIS: Maximal Independent Set

The "Greedy" Algorithm (Centralized)

How it works:

The Challenge: Symmetry Breaking

The Biological Coordination Problem

How Symmetry Is Broken in the Fly

From Biology to Algorithm

The Key Insight: Rate Change

Algorithm in Action

Algorithm Parameters

MIS Algorithm

Lemma 1: Independence

Lemmas 2 & 3: Exiting the Algorithm

Lemma 4: Degree Reduction

The Logic (Proof Sketch)

What makes this special?

Standard Algorithms

Fly Algorithm

Comparison: Bandwidth

Standard: Log(N) bits

Fly Algorithm: 1 bit

Robustness: Handling Failure

The "Crash" Scenario

The Biological Way

Application 1: Sensor Networks

Why the Fly Algorithm?

Application 2: Swarm Robotics

Decentralized Control

Dynamic Environment

The Future: Algorithms in Nature

Ants

Bees

Flies

Limitations & Considerations

Probabilistic Nature

Synchronization

Energy vs Speed

Summary

"Simplicity is the ultimate sophistication."

References

Q & A

DESIGNER-MADE PRESENTATION, GENERATED FROM YOUR PROMPT

Biological Algorithms: Bio-Inspired Maximal Independent Set

DESIGNER-MADE
PRESENTATION,
GENERATED FROM
YOUR PROMPT