Determination of the topology of a directed network
Darin Goldstein · 2002
We consider strongly-connected, directed networks of identical synchronous, finite-state processors with in- and out-degree uniformly bounded by a network constant. Via a straightforward extension of R. Ostrovsky and D. Wilkerson's backwards communication algorithm (1995), we exhibit a protocol which solves the global topology determination problem, the problem of having a root processor map the global topology of a network of. unknown size and topology, with running time O(ND) where N represents the number of processors and D represents the diameter of the network. A simple counting argument suffices to show that the global topology determination problem has time-complexity /spl Omega/(N log N) which makes the protocol presented asymptotically time-optimal for many large networks.