Existence of Deadlock-Free Routing for Arbitrary Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909527995056128 |
|---|---|
| author | Mendlovic, Uri Matias, Yossi |
| author_facet | Mendlovic, Uri Matias, Yossi |
| contents | Given a network of routing nodes, represented as a directed graph, we prove the following necessary and sufficient condition for the existence of deadlock-free message routing: The directed graph must contain two edge-disjoint directed trees rooted at the same node, one tree directed into the root node and the other directed away from the root node.
While the sufficiency of this condition is known, its necessity, to the best of our knowledge, has not been previously recognized or proven. Although not directly applicable to the construction of deadlock-free routing schemes, this result provides a fundamental insight into the nature of deadlock-free networks and may lead to the development of improved tools for designing and verifying such schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04583 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Existence of Deadlock-Free Routing for Arbitrary Networks Mendlovic, Uri Matias, Yossi Combinatorics Distributed, Parallel, and Cluster Computing Networking and Internet Architecture Given a network of routing nodes, represented as a directed graph, we prove the following necessary and sufficient condition for the existence of deadlock-free message routing: The directed graph must contain two edge-disjoint directed trees rooted at the same node, one tree directed into the root node and the other directed away from the root node. While the sufficiency of this condition is known, its necessity, to the best of our knowledge, has not been previously recognized or proven. Although not directly applicable to the construction of deadlock-free routing schemes, this result provides a fundamental insight into the nature of deadlock-free networks and may lead to the development of improved tools for designing and verifying such schemes. |
| title | Existence of Deadlock-Free Routing for Arbitrary Networks |
| topic | Combinatorics Distributed, Parallel, and Cluster Computing Networking and Internet Architecture |
| url | https://arxiv.org/abs/2503.04583 |