We analyze the correctness and the complexity of two well-known routing algorithms, introduced by Gafni and Bertsekas (1981): By reversing the directions of some edges, these algorithms transform an arbitrary directed acyclic input graph into an output graph with at least one route from each node to a special destination node (while maintaining acyclicity). The resulting graph can thus be used to route messages in a loop-free manner. Gafni and Bertsekas implement these algorithms by assigning to each node of the graph an unbounded "height" in some total order. The relative order of the heights of two neighboring nodes induces a logical direction on the edge between them; the direction of an edge is reversed by modifying the height of one endpoint. In this work, we present a novel formalization for these algorithms based only on directed graphs with binary labels for edges. Using this formalization, we define a distributed algorithm for establishing routes in acyclic graphs, and we derive requirements on the input graph for correctness of the algorithm. The algorithms of Gafni and Bertsekas are special cases of our more general algorithm. Moreover, this simple formalization allows us to give an exact complexity analysis. In particular, we provide an expression for the exact number of steps taken by each node during an execution of the algorithm, and prove that this complexity only depends on the input graph. Copyright 2009 ACM.
name of conference
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures
