Linear sure bootstraper: Self-stabilizing nodes for network construction

An overlay network’s efficiency can be improved by taking advantage of its network structure. However, before a structured network can be constructed, nodes has to be topologically sorted. One of the common form of topological sorting is linearization where nodes are arranged in a linear order with respect to its identifiers. Linearization is not a difficult task, however, to keep nodes in a correct state where transient faults exist can be daunting. In this paper, we introduce an algorithm to improve the performance of an overlay network by ensuring physical proximity and the introduction of supernodes (nodes that are homogeneous to other nodes but remain persistent). We construct a linear network from a random distribution of nodes in a 2-D geographical space and run simulations to test our algorithm. Our experiments shows that our algorithm scales linearly as the number of nodes increases and supernodes reduces the cycle time for linearization