A self-stabilizing algorithm for the st-order problem

Given a biconnected graph G with n nodes and a pair of unique nodes s and t, an st-ordering assigns s with 1 and t with n, and every other node with an integer between 2 and n - 1 (inclusive) such that it has at least one neighbor with a smaller number and at least one neighbor with a larger number. This paper presents a self-stabilizing distributed algorithm which assigns an st-ordering to G. The algorithm is shown to require at most O(n log n) rounds to converge to a correct solution.