The columns in the Figure above represent the following information:

  • Column A shows the consecutive core node numbers in a network with 32 core nodes in total
  • Column B shows the binary representation of the core node numbers from column A (five bits in total)
  • Column C shows the numbers of the five successive exchange partners of each core node, found by toggling the five bits of column B one by one.
  • Column D shows the total number of accumulated contributions after each of the five exchange cycles
  • Column E first shows node numbers of helpers from which a better result may be downloaded, and in the last column it shows what result is achieved after that repair action.

In this first example, core node number 9 goes off-line before the completion of exchange cycle 3 of the square dance exchange process. Its exchange partner in the cycle is node number 13, which will have an incomplete accumulation result after cycle 3 (...in column D, there are only 4 contributions after cycle 3, because the four additional contributioins that should have come from node 9 have never arrived at node number 13).

In the fourth exchange cycle, the exchange partner of node 9 would have been node 11, which expects to get 8 contributions from node 9. instead, its data request times out, and node 11 continues to cycle five without receiving anything from node 9. In column D, it shows how node 11 misses 8 contributions after cycle 4.

Also in the fourth cycle, the exchange partner of node 13 is node number 15. Instead of 8 contributions, it only receives 4 contributions from node 13, because the inputs from node 9 (in cycle 3) have never arrived.

It will be clear how the anomaly in cycle three affects 2 nodes (9, 13) in cycle 3, then 4 nodes (9, 13, 11, 15) in cycle four, etc. After completion of cycle 5, there are 8 nodes that do not have the correct (maximum) number of accumulated contributions, and they know it. The actual number of contributions that each node is missing is not the same for each node but they all knew that there should hve been 32 contributions after cycle 5. the different colors indicate how the anomaly spreads out through the "downstream" network of node 9.

The nodes with incomplete accumulation results now look at the five other network nodes to which they are connected. In this simple case, they all see at least two neighbours with a perfect result (namely, the maximum possible number of ocntributions of 32) and immediately download this result from these neighbours. This means that after just one repair transaction, all remaining 31 network nodes have found an accumulation results based on all 32 results. The remarkable aspect of this is that the original input information from node 9 still reaches all other nodes in the network, even after the moment that node 9 itself has died.

Project details

Ultimate Browsers SupportThe GPS Dancer project started in 2007 as a voluntary project of a working group of the International Association of Geodesy.

Read more ...

Square dance algorithm

Great Docs and SupportThe GPS Dancer system was named after its "square dance" exchange algorithm. Of course, it also wants to to make the GPS reference frame denser.

Read more...

Here, there be pirates

The Dancer on-line network became immune against internet connection problems by leaving the US marines, and becoming a pirate.

Read more ...

Go to top