A simple self-stabilizing replication algorithm

A replication algorithm aims at keeping a number of copies of a data item mutually consistent. Here's a first algorthm that completes this task.

A primary copy processor updates it's copy of the replication data. The algorithm ensures that these changes will eventually be received by all other replicas in the network resulting in a consistent state after a certain period of time. The protocol used here is similar to Richard Golding's timestamped anti-entropy framework. For a detailed analysis and comparison, see my diploma thesis.

The Applet

The following applet implements the simple algorithm using simjava. The topmost node (node A ) contains the primary copy of the replication item. The data displayed next to the nodes has the following meaning:

• The character at the top left corner is the name (identity) of the node.
• The number in brackets beside it is the current value of the local replica, so for example B(5) means that the local replica value node B currently is 5.
• nbs = {...} designates the up-neighbours set (i.e. those neighbouring nodes which are currently reachable)
• parent = X means that the parent node in the spanning tree is currently node X.
• level = y shows the current level that the node has in the tree.

You may click on the nodes and channels to select various different kinds of faults. To globally perturb the system state, try pressing the ``reset all'' or ``perturb all'' buttons on the top panel and see how the system converges to a ``good'' state againin which the changes done by the primary copy (A) eventually duffuse to all stations. Note that the applet will stay silent for about 50 simulation time units before any visible action takes place. (This is due to an internal timeout of the algorithm that keeps the system alive in cases where all action has ceased.)

You may have a look at

• the applet's ``notangled'' source code (without documentation)
• the applet's ``noweaved'' source code in HTML format (using noweb's hypertext abilities)
• the applet's ``noweaved'' source code as a .dvi file