Maximal Independent Set: A Biological Algorithm Solution
Explore how biological processes in fruit flies solve the Maximal Independent Set (MIS) problem in distributed computing without a central controller.
Maximal Independent Set
A Biological Solution to a Distributed Computing Problem
Yaman Dahle, Leen Hassan
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.
Informal Problem Definition
We consider a distributed system in which processors jointly solve a task without any processor seeing all inputs. Each processor communicates only with its immediate neighbors.
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.
MIS: Maximal Independent Set
Independence
No two nodes in set A are directly connected (A is an independent set).
Maximality
Every node in the network is either in A or directly connected to a node in A.
The 'Greedy' Algorithm (Centralized)
Pick a node → Add to Set A.
Remove its neighbors.
Repeat until graph is empty.
The Problem: It is Sequential (needs a central ID/Boss). We need a Parallel solution.
The Challenge: Symmetry Breaking
Imagine all nodes are identical. They run the same code and wake up at exactly the same time.
If Node A decides 'I'll join!', its neighbor Node B does the exact same thing. Deterministic decisions lead to conflicts.
Solution: Introduce randomness so nodes make different decisions.
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.
How Symmetry Is Broken in the Fly
All cells start in the same state.
Small random differences appear.
A cell slightly ahead inhibits its neighbors.
Inhibition amplifies the difference.
Outcome: A single SOP is selected from a symmetric group.
From Biology to Algorithm
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.
The Key Insight: Rate Change
Traditional algorithms need to know the number of neighbors (degree). Cells don't know their degree.
1. Start with a very low probability of speaking up.
2. Gradually increase the probability over time.
This avoids an initial 'shouting match' (collisions).
Algorithm in Action
1. Broadcast (Red)
Center node wakes up and yells 'BEEP!'
2. Inhibit (Yellow)
Neighbors hear the beep and must stay 'Quiet'.
3. Parallel Leaders
Distant nodes can become LEADERS simultaneously. This is how it scales!
- distributed-computing
- maximal-independent-set
- algorithms
- biomimicry
- symmetry-breaking
- computer-science
- parallel-processing