This example implements a spanning forest algorithm based on the circulation of tokens.
The algorithm relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk inside the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly.
The demo can be launched in the top-right corner of this page.
Details can be found in these two papers:
A. Casteigts, S. Chaumette, F. Guinand, and Y. Pigné,
Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks,
10th International Conference on Adhoc, Mobile, and Wireless Networks (ADHOC-NOW), 2013.
M. Barjon, A. Casteigts, S. Chaumette, C. Johnen, and Y.M. Neggaz,
Maintaining a Spanning Forest in Highly Dynamic Networks: The Synchronous Case,
18th Int. Conference on Principles of Distributed Systems (OPODIS), 2014.
The first paper adapts the algorithm in a coarse-grain interaction model, while the second does it in a (synchronous) message passing model.