A simulation of the algorithm from "A Biological Solution to a Fundamental Distributed Computing Problem" by Afek, Alon, Barad, Hornstein, Barkai, and Bar-Joseph. Primitive nodes, following a simple probabilistic broadcast/receive procedure, elect a maximal independent set with very high probability. This new algorithm is inspired by processes in the developing nervous system of a fly!
After broadcasting in exchange 1, if a node has received no broadcasts from neighbors, then in exchange 2 the node joins the MIS and broadcasts to its neighbors, signalling they should exit the algorithm.
In any given exchange step, the probability a node may broadcast to its neighbors is a function of the current phase and the upper bound on the number of neighbors a node in the network may have. It increases over time.
In this visualization red nodes are members of the MIS, while blue nodes are not (this is backwards from illustrations in the paper I've just realized). When nodes turn red or blue they have become inactive.
Here is my blog post introducing this project in more detail.
Running exchange 1,
in step 0 of ,
in phase 0 of ,
with broadcast probability %.