# Maximal Independent Set: A Bio-Inspired Algorithm Guide
> Explore how biology helps solve the Maximal Independent Set (MIS) problem in distributed systems using symmetry breaking and the fly's sensory organ cells.

Tags: distributed-computing, algorithms, maximal-independent-set, bio-inspired, symmetry-breaking, parallel-computing, computer-science
## Maximal Independent Set | A Biological Solution to a Distributed Computing Problem
* Authors: Yaman Dahle, Leen Hassan
* Explores MIS in Wi-Fi networks, sensors, and traffic systems.

## Why MIS Matters?
* Helps systems work without a central controller (no boss).
* Avoids interference by ensuring critical units (routers) are not too close while maintaining coverage.

## Formal Problem Definition
* Goal: Select a subset of processors such that no two neighbors are selected, and every processor is either selected or adjacent to a selected node.

## The Greedy vs. Parallel Challenge
* Centralized algorithms pick nodes sequentially, which requires a 'boss'.
* Distributed systems face the 'Symmetry Breaking' problem where identical nodes making identical decisions leads to conflict.

## The Biological Coordination Solution
* Based on how fly cells decide which becomes a sensory organ (SOP).
* Nearby cells use inhibition to ensure only one leader is chosen from a group of identical candidates.
* Key mechanism: Small random differences amplified by local inhibition.

## From Biology to Algorithm
* Nodes behave like cells with probabilistic (random) decision-making.
* Rate Change Insight: Nodes start with a low 'speaking' probability that increases gradually to avoid initial collisions ('shouting matches').
* Graph Data: Probability of Broadcast increases from 0.01 in Phase 1 to 0.16 in Phase 5.

## Algorithm in Action
* 3-Step Cycle: Broadcast (Beep), Inhibit (Stay quiet), and Parallel Leadership selection.
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.