# Maximal Independent Set: A Bio-Inspired Distributed Algorithm
> Learn how fruit fly biology inspires solutions for Maximal Independent Set (MIS) in distributed systems to avoid interference and manage decentralization.

Tags: maximal-independent-set, distributed-computing, algorithm, bio-inspired, symmetry-breaking, parallel-computing, network-topology
## Maximal Independent Set (MIS)
* **Topic**: A biological solution to a distributed computing problem.
* **Authors**: Yaman Dahle, Leen Hassan.

## Why MIS Matters?
* **Decentralization**: Allows systems like Wi-Fi networks to organize without a central controller.
* **Interference**: Ensures critical units are spaced out to prevent signal conflicts while maintaining coverage.

## Global Problem Definition
* **Goal**: Select a subset of processors where no two neighbors are selected, but every processor is either selected or adjacent to a selected one.
* **Constraints**: Processors have zero global knowledge and communicate only with neighbors.

## Formal Definition: MIS
1. **Independence**: No two nodes in set A are directly connected.
2. **Maximality**: Every node is either in set A or connected to a node in A.

## The Problem with Greedy Algorithms
* Sequential approach requires a central coordinator.
* Large networks require parallelism, which greedy algorithms lack.

## Symmetry Breaking Challenge
* Identical nodes running identical code can lead to deterministic deadlocks if they all attempt to join the set at once.

## Biological Inspiration: The Fruit Fly
* During development, identical cells must decide which become sensory organs (SOPs).
* Neighboring cells cannot both be SOPs; a pattern emerges without a central brain.

## How Nature Breaks Symmetry
1. **Uniform Start**: Cells start in the same state.
2. **Random Differences**: Natural molecular fluctuations.
3. **Inhibition**: A leading cell inhibits its neighbors.
4. **Amplification**: The leader grows stronger while neighbors stay quiet.

## Mapping Biology to Code
* Nodes act as cells.
* **Probabilistic Logic**: Replaces deterministic rules with "biological noise."
* **Message Passing**: Handled via lateral inhibition simulation.

## Key Insight: The Rate Change
* Instead of knowing neighbor counts, probabilities are increased exponentially over time.
* Probability phases: Phase 1 (0.01) to Phase 5 (0.16) to avoid early collisions.

## Algorithm Execution
1. **Broadcast**: A node signals 'BEEP' based on its probability.
2. **Inhibit**: Neighbors hearing the signal drop out.
3. **Parallelism**: Distant nodes can lead simultaneously, allowing massive scaling.
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.