# 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.

Tags: distributed-computing, maximal-independent-set, algorithms, biomimicry, symmetry-breaking, computer-science, parallel-processing
## Maximal Independent Set: A Biological Solution to a Distributed Computing Problem
* Authors: Yaman Dahle, Leen Hassan

## Why MIS Matters?
* Helps systems work without a central boss (Wi-Fi, sensors, traffic systems).
* Prevents interference and conflicts by ensuring controllers are not too close while still providing coverage.

## Informal Problem Definition
* Goal: Select a subset of processors where no two neighboring processors are selected, and every processor is either selected or adjacent to a selected one.
* Constraints: Processors communicate only with immediate neighbors; no processor sees all inputs.

## MIS Components
* **Independence**: No two nodes in the set are directly connected.
* **Maximality**: Every node in the network is either in the set or connected to one that is.

## The Sequential Problem
* Greedy algorithms work by picking a node and removing neighbors, but they require a central 'Boss' or ID and are sequential.
* Challenge: **Symmetry Breaking**. Identical nodes making deterministic decisions lead to conflicts.

## The Biological Inspiration
* Fruit fly development: Identical cells decide which become sensory organs (SOPs).
* Dilemma: Neighboring cells cannot both be leaders.
* Solution: Small random differences and local inhibition amplify differences to select single leaders within groups.

## From Biology to Algorithm
* Nodes mimic cells using probabilistic decisions.
* **Key Insight: Rate Change**. Start with a low probability of 'speaking up' (broadcast p=0.01) and gradually increase it over phases (up to p=0.16) to avoid initial collisions.

## Algorithm Steps
1. **Broadcast (Red)**: A node wakes up and signals neighbors.
2. **Inhibit (Yellow)**: Neighbors hearing the signal stay quiet.
3. **Parallel Leaders**: Distant nodes become leaders simultaneously to allow the system to scale.
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.