Adaptive Spanning-tree on Changing Topologies: Towards Emergent Behaviors in Autonomous Multi-Agent Systems

We propose a method to make a population of autonomous agents build and maintain a directed spanning tree architecture on a changing communication topology. Currently known algorithms can build a spanning tree in a distributed fashion in R times, where R is the radius of the spanning tree, provided the topology remains fixed during this time span. Our method removes this latter condition. To this end, we use a discrete wave equation on a grounded graph, prove a property of its eigenfunctions and exploit it. Our algorithm beats the Spanning Tree Protocol IEEE 802.1, the current standard for local area networks in terms of resilience to topology changes.