Stephan Holzer: The Power of a Leader in the Stone Age

It is known that in cellular networks modeled by the stone age model of distributed computing [PODC 2013] certain computations are not possible. This includes electing a leader, computing shortest paths and the diameter of a graph [STOC 1980],[ICALP 2014]. However, certain organisms such as the true slime mold Physarum polycephalum seem to be able to compute shortest paths [Nature 2000] and structures close to minimum spanning trees [Science 2010]. When such an organism is modeled using the stone age model, this behavior is only possible when a leader is available. In a first attempt to explain the true slime molds abilities using the stone age model we equip the cellular network with a leader and show that this enables the network to identify cells of maximal distance to each other, compute shortest path and minimum spanning trees.