Self-stabilizing sorting on linear networks

A self-stabilizing system has the ability to recover from an arbitrary (possibly faulty) state to a normal state without any manual intervention. A self-stabilizing algorithm does not require any initialization. Starting from an arbitrary state, it is guaranteed to satisfy its specification in finite number of steps; We propose a self-stabilizing distributed sorting algorithm on an oriented linear network with n nodes. Each node holds some initial value(s) drawn from an arbitrary set. We assume that we start with at most k items in the network. Each node has a local memory whose space is restricted to O(k * L ) where L is the maximum number of bits to store one item. A node may collect more than one value during the process of sorting. The stabilizing time for sorting is O(n) rounds where a round is the duration for all the enabled processes to execute at least one enabled step. We claim that our algorithm is self-stabilizing for the following reasons:;If any node starts in a faulty state (meaning its value is not sorted with respect to its neighbors), the algorithm guarantees that the node will reach the legitimate state (where a legitimate state is a state in which the values are in sorted order) in a finite amount of time, and will remain in the legitimate state until another fault occurs. Each node repeatedly communicates with its neighbors to check if the values of its neighbors are sorted with respect to its own value. If the values are not in order, either the node or one of its neighbors will eventually be enabled to execute so that in finite amount of time the values will be sorted