Edge-Disjoint Spanning Trees on Star-Product Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913835633344512 |
|---|---|
| author | Isham, Kelly Monroe, Laura Lakhotia, Kartik Dawkins, Aleyah Hwang, Daniel Kubicek, Ales |
| author_facet | Isham, Kelly Monroe, Laura Lakhotia, Kartik Dawkins, Aleyah Hwang, Daniel Kubicek, Ales |
| contents | A star-product operation may be used to create large graphs from smaller factor graphs. Network topologies based on star-products demonstrate several advantages including low-diameter, high scalability, modularity and others. Many state-of-the-art diameter-2 and -3 topologies~(Slim Fly, Bundlefly, PolarStar etc.) can be represented as star products.
In this paper, we explore constructions of edge-disjoint spanning trees~(EDSTs) in star-product topologies. EDSTs expose multiple parallel disjoint pathways in the network and can be leveraged to accelerate collective communication, enhance fault tolerance and network recovery, and manage congestion.
Our EDSTs have provably maximum or near-maximum cardinality which amplifies their benefits. We further analyze their depths and show that for one of our constructions, all trees have order of the depth of the EDSTs of the factor graphs, and for all other constructions, a large subset of the trees have that depth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12231 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge-Disjoint Spanning Trees on Star-Product Networks Isham, Kelly Monroe, Laura Lakhotia, Kartik Dawkins, Aleyah Hwang, Daniel Kubicek, Ales Networking and Internet Architecture Distributed, Parallel, and Cluster Computing Combinatorics A star-product operation may be used to create large graphs from smaller factor graphs. Network topologies based on star-products demonstrate several advantages including low-diameter, high scalability, modularity and others. Many state-of-the-art diameter-2 and -3 topologies~(Slim Fly, Bundlefly, PolarStar etc.) can be represented as star products. In this paper, we explore constructions of edge-disjoint spanning trees~(EDSTs) in star-product topologies. EDSTs expose multiple parallel disjoint pathways in the network and can be leveraged to accelerate collective communication, enhance fault tolerance and network recovery, and manage congestion. Our EDSTs have provably maximum or near-maximum cardinality which amplifies their benefits. We further analyze their depths and show that for one of our constructions, all trees have order of the depth of the EDSTs of the factor graphs, and for all other constructions, a large subset of the trees have that depth. |
| title | Edge-Disjoint Spanning Trees on Star-Product Networks |
| topic | Networking and Internet Architecture Distributed, Parallel, and Cluster Computing Combinatorics |
| url | https://arxiv.org/abs/2403.12231 |