A self-stabilizing algorithm for the st-order problem
Pranay Chaudhuri, Hussein Thompson · International Journal of Parallel Emergent and Distributed Systems · 2008
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.