Selfstabilizing Random Graph

This implementation uses d3sf.

Problem description

We have a weak connected random distributed directed graph/network. We are searching for an distributed algorithm to stabilize this random graph to a connected graph. We assume that there are no edge removes while stabilizing.

Short description of the algorithm

Every newly inserted edge triggers a so called backrouting (at graph initializing every edge is new, so for every edge a backrouting is started). Before starting the backrouting, we have to insert some temporary nodes. For every edge (a,b) we have a temporary edge (b,a).
Let's take an example now. We have nodes A and B. A has an edge to B. B inserts an temporary edge to A. At this point both nodes communicate the maximal route length they know. Then the backrouting message, that consists of origin, aim and hops. In our example the origin is B, the aim A and hops at the beginning 1. This message is broadcasted from every node that receives this message for the first time. The broadcasting excludes the temporary edges. At every broadcasting step, the hops is increased. When a node sees a higher hops count than he stored as maximal route length, that node broadcasts this new information over every edge (inclusively temporary edges). When the aim node receives this message, it stores the node as stable. In our example, A would store B as stable neighbour. If A doesn't receive this message, A has a timeout of 2 * maximal_route_length + 1. After this time it is sure, that B had no route to A. So we know that the graph is weak connected. So we are searching for a new neighbour for B to fix this problem. Therefor A sends out a neighboursearch message to one of his stable neighbours or over a temporary edge. Through that we can assure that the new neighbour will not be in a part where no route to A exists. The neighboursearch message has a hops counter. The current receiver of the message will be the new neighbour of B with a probability of hops / maximal_route_length. Else the message is send further. After that we have a new edge from B to somewhere else. The graph is connected now and everything is fine :).

Complexity

The message complexity is O(|E|²).
The time complexity is only O(|E|).

Downloads

• German presentation from my sister
• doxygen pdf
• doxygen html
• d3sf with algorithm

Compiling

That is very easy. Change to the extracted directory and execute make.

License

/*
 * Copyright (C) 2010 scosu (http://allfex.org)
 *
 * This file is part of d3sf.
 *
 * d3sf is a framework to simulate synchronous distributed systems.
 *
 *
 * d3sf is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * d3sf is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with libudpox.  If not, see <http://www.gnu.org/licenses/>.
 */