A fault-tolerant distributed sorting algorithm in tree networks

The paper presents a distributed sorting algorithm for a network with a tree topology. The distributed sorting problem can be informally described as follows: nodes cooperate to reach a global configuration where every node, depending on its identifier, is assigned a specific final value taken from a set of input values distributed across all nodes; the input values may change in time. In our solution, the system reaches its final configuration in a finite time after the input values are stable and the faults cease. The fault tolerance and adaption to changing input are achieved using Dijkstra´s paradigm of self stabilization. Our solution is based on continuous broadcast with acknowledgment along the tree network to achieve synchronization among processes in the system; it has O(nh) time complexity and only O(log(n)deg) memory requirement where deg is the degree of the tree and h is the height of the tree