Parallel construction of multiple independent spanning trees on highly scalable datacenter networks
作者：
Highlights：
• We prove that a highly scalable data center network (HSDC) is vertex-symmetric.
• We investigate the independent spanning trees (IST) problem on HSDC.
• We propose an algorithm to construct n ISTs on the n-dimensional HSDC, denoted as HSn.
• The algorithm can be parallelized to run in O(n) time using N=2n processors.
• As a by-product, we obtain the connectivity ofHSn to be n.
摘要
•We prove that a highly scalable data center network (HSDC) is vertex-symmetric.•We investigate the independent spanning trees (IST) problem on HSDC.•We propose an algorithm to construct n ISTs on the n-dimensional HSDC, denoted as HSn.•The algorithm can be parallelized to run in O(n) time using N=2n processors.•As a by-product, we obtain the connectivity ofHSn to be n.
论文关键词：Datacenter networks,Independent spanning trees,Parallel algorithms,Fault-tolerant broadcasting,Secure message distribution
论文评审过程：Received 15 April 2021, Revised 17 August 2021, Accepted 18 August 2021, Available online 30 August 2021, Version of Record 30 August 2021.
论文官网地址：https://doi.org/10.1016/j.amc.2021.126617
