Determination of the Topology of a Directed Network

Title: Determination of the Topology of a Directed Network

Research Question: Can we develop an efficient protocol to determine the global topology of a large, directed network of processors with limited communication capabilities?

Methodology: The researchers proposed a protocol that extends Ostrovsky and Wilkerson's Backwards Communication Algorithm. This protocol allows processors to determine the global topology of the network by communicating with their neighbors.

Results: The researchers showed that their protocol solves the Global Topology Determination Problem, which involves determining the global topology of a network of unknown size and topology. They proved that the protocol has a time-complexity of O(ND), where N represents the number of processors and D represents the diameter of the network. A simple counting argument further confirmed that the problem has a time-complexity of Ω(NlogN), making the protocol presented asymptotically time-optimal for many large networks.

Implications: This research has significant implications for networks with limited communication capabilities. The protocol provides an efficient way to determine the global topology of such networks, which is crucial for various network applications. The protocol's time-complexity guarantees that it can be used for large networks, making it a practical solution for real-world scenarios.

Link to Article: https://arxiv.org/abs/0310004v1 Authors: arXiv ID: 0310004v1