Linear Sure Bootstraper: Self-Stabilizing Nodes For Network Construction

摘要

An overlay network's efficiency can be improvedby taking advantage of its network structure. However, beforea structured network can be constructed, nodes has to be topologicallysorted. One of the common form of topological sortingis linearization where nodes are arranged in a linear order withrespect to its identifiers. Linearization is not a difficult task,however, to keep nodes in a correct state where transient faultsexist can be daunting. In this paper, we introduce an algorithmto improve the performance of an overlay network by ensuringphysical proximity and the introduction of supernodes (nodesthat are homogeneous to other nodes but remain persistent).We construct a linear network from a random distributionof nodes in a 2-D geographical space and run simulations totest our algorithm. Our experiments shows that our algorithmscales linearly as the number of nodes increases and supernodesreduces the cycle time for linearization.