# MIS Algorithm: From Biological Inspiration to Computation
> Explore how the fruit fly's SOP selection inspires efficient distributed Maximal Independent Set (MIS) algorithms for wireless networks and processors.

Tags: mis-algorithm, distributed-systems, biology-inspired-computing, maximal-independent-set, symmetry-breaking, algorithm-complexity, wireless-networks
## Maximal Independent Set (MIS): From Biology to Computation
* Presenters: Leen Hassan, Yaman Dahle

## Why MIS Matters?
* Backbone for wireless networks
* Efficient message routing
* Clustering and selecting local leaders without central authority
* Scalable ad-hoc sensor networks

## Formal Definition of MIS
* Given Graph G = (V, E), subset A ⊆ V is MIS if:
  1. Independence: No two nodes in A are neighbors.
  2. Dominance: Every node outside A has a neighbor in A.

## The Challenge: Symmetry Breaking
* Distributed systems lack global knowledge.
* Identical nodes might collide or deadlock without central coordination.
* Solution: Randomization (flipping coins) allows fast local decisions.

## Biological Inspiration: SOP Selection
* In fruit fly development, cells decide which become sensory organs (SOPs).
* Mechanism: Lateral Inhibition. Once a cell is selected, it inhibits neighbors.
* Result: An exact MIS pattern emerges naturally using 1-bit communication.

## The Rate Change Model
* Unlike traditional algorithms (Luby's), cells don't know their neighbor count (degree).
* Solution: Start with low probability of broadcast and gradually increase it to avoid initial collisions ('shouting matches').

## Formal MIS Algorithm (n, D)
* Outer loop phase $i$ from 0 to $\log D$.
* Inner loop $j$ from 0 to $M \log n$.
* Exchange 1: Broadcast with probability $1/2^{(\log D - i)}$.
* Exchange 2: If node broadcast alone, join MIS and notify neighbors to become inactive.

## Complexity Analysis
* **Time Complexity:** $O(\log D \cdot \log n)$, which is $O(\log^2 n)$ since $D \le n$.
* **Message Complexity:** Optimal expected linear number of messages $O(n)$ using constant-size (1-bit) signals.

## Summary
* Local randomness replaces global control.
* Biology inspires fast, scalable, and communication-efficient distributed algorithms.
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.