pith. sign in

arxiv: 2606.23935 · v1 · pith:LEZYSU63new · submitted 2026-06-22 · 💻 cs.DC

An Efficient Construction of Completely Independent Spanning Trees in Dense Gaussian Networks

Zaid Hussain , Fawaz AlAzemi , Bader AlBdaiwi This is my paper

Pith reviewed 2026-06-26 06:39 UTC · model grok-4.3

classification 💻 cs.DC
keywords completely independent spanning treesdense Gaussian networksCIST constructionfault tolerancenetwork partitioningrotation methodbroadcasting efficiencyinterconnection networks
0
0 comments X

The pith

Partitioning nodes and rotating connections produces two completely independent spanning trees in dense Gaussian networks with the second having smaller depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to construct two completely independent spanning trees in dense Gaussian networks to improve fault tolerance in routing and broadcasting. It partitions the network into sets and connects the nodes to form the first CIST. A rotation is then applied to generate the second CIST. This second tree has less depth than those from existing methods. The average maximum number of steps to deliver a message from the root to all other nodes improves by at least 33 percent.

Core claim

By partitioning the dense Gaussian network into sets to form the first CIST and then rotating to obtain the second CIST with strictly smaller depth, the method yields two completely independent spanning trees that outperform prior constructions by at least 33 percent in average maximum message delivery steps.

What carries the argument

The rotation step applied to the first CIST, which produces a second CIST that is edge-disjoint and vertex-disjoint with strictly smaller depth.

If this is right

  • Improved fault tolerance and reliability for routing and broadcasting in failure-prone networks.
  • Lower average maximum steps required to deliver messages from root to all nodes.
  • Greater communication efficiency in large-scale interconnection systems.
  • Outperformance of existing state-of-the-art constructions by at least 33 percent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The partitioning-plus-rotation approach may extend to constructing CISTs in other regular network topologies if analogous sets can be defined.
  • Smaller depth in the second tree could reduce latency in fault-free broadcasting, though the paper measures only the fault-tolerance metric.
  • The construction could be tested on progressively larger network sizes to verify whether the 33 percent improvement holds as scale increases.

Load-bearing premise

The rotation step applied to the first CIST automatically produces a second CIST that remains completely edge-disjoint and vertex-disjoint from the first while also having strictly smaller depth.

What would settle it

A concrete counterexample in a dense Gaussian network where the rotated structure shares an edge or vertex with the first CIST or fails to have smaller depth or shows less than 33 percent improvement in average maximum delivery steps.

read the original abstract

Fault tolerance in routing and broadcasting is a critical aspect in ensuring the reliability and robustness of communication networks, particularly in environments prone to failures. This work presents an efficient method for constructing Completely Independent Spanning Trees (CISTs) within dense Gaussian networks, providing improved fault tolerance, reliability, and communication efficiency in large-scale interconnection systems. To construct the CISTs in the Gaussian network, we partition the network into sets, and accordingly the nodes are connected properly to form the first CIST and then rotated to get the second CIST with less depth than the existing state-of-art. To evaluate the performance of the proposed construction, we calculated the average maximum number of steps required to deliver a message from the root node to all other nodes in the network. A comparison with existing approaches shows that our construction outperforms them, achieving an improvement of at least 33%

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims an efficient construction of two completely independent spanning trees (CISTs) in dense Gaussian networks: the network is partitioned into sets whose nodes are connected to form a first CIST; a rotation is then applied to obtain a second CIST of strictly smaller depth. Performance is assessed via the average maximum number of delivery steps from the root, with the abstract asserting that the construction outperforms prior work by at least 33%.

Significance. If the rotation is shown to preserve spanning-tree validity, complete independence (edge- and vertex-disjointness except at the root), and reduced depth, and if the 33% figure is backed by an explicit formula and reproducible comparison, the result would supply a concrete, implementable improvement in fault-tolerant routing for Gaussian networks, a topology used in large-scale interconnection systems.

major comments (2)
  1. [Abstract] Abstract: the central performance claim ('improvement of at least 33%') is stated without any formula for 'average maximum number of steps,' without numerical values, and without a comparison table or reference to prior constructions. This leaves the quantitative assertion unsupported.
  2. [Construction] Construction description (partition-and-rotate method): no explicit rotation rule is supplied, nor is any argument or lemma given that the rotated structure remains a spanning tree, shares no edges or non-root vertices with the first tree, and has strictly smaller depth. These three properties are load-bearing for both the CIST claim and the depth-reduction claim.
minor comments (1)
  1. [Abstract] The abstract refers to 'dense Gaussian networks' without citing the precise definition or parameter range used in the construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments. We address the major comments below and will make the necessary revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central performance claim ('improvement of at least 33%') is stated without any formula for 'average maximum number of steps,' without numerical values, and without a comparison table or reference to prior constructions. This leaves the quantitative assertion unsupported.

    Authors: We agree with this observation. The abstract currently provides only a high-level statement of the improvement. In the revised manuscript, we will expand the abstract to include the definition of the 'average maximum number of steps' metric, the specific numerical values obtained from our evaluations, and explicit references to the prior constructions being compared, along with the basis for the at least 33% improvement figure. This will make the performance claim fully supported. revision: yes

  2. Referee: [Construction] Construction description (partition-and-rotate method): no explicit rotation rule is supplied, nor is any argument or lemma given that the rotated structure remains a spanning tree, shares no edges or non-root vertices with the first tree, and has strictly smaller depth. These three properties are load-bearing for both the CIST claim and the depth-reduction claim.

    Authors: The current manuscript provides a concise description of the partition-and-rotate method. We acknowledge that more detail is needed. In the revision, we will include the explicit rotation rule used in the construction. Additionally, we will add formal arguments or lemmas demonstrating that the rotated structure is indeed a spanning tree, that it is completely independent from the first tree (i.e., edge-disjoint and vertex-disjoint except at the root), and that it has strictly smaller depth. These additions will be placed in the construction section to rigorously support the claims. revision: yes

Circularity Check

0 steps flagged

No circularity; construction is algorithmic and externally benchmarked

full rationale

The paper describes an explicit construction (partition the dense Gaussian network, connect nodes to form the first CIST, then rotate to obtain the second) whose correctness and performance are asserted by direct comparison to prior published constructions. No equations, fitted parameters, self-definitional loops, or load-bearing self-citations appear in the abstract or the described method. The central performance claim (≥33% improvement in average maximum delivery steps) is framed as an empirical comparison rather than a derivation that reduces to its own inputs. The rotation step is presented as part of the construction, not as a prediction derived from the first tree by algebraic identity. This is the normal case of a self-contained algorithmic result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on standard assumptions from graph theory about the existence of spanning trees in connected regular graphs and on the geometric properties of Gaussian networks that permit a consistent rotation operation.

axioms (1)
  • domain assumption Dense Gaussian networks admit a partition into node sets that each induce a spanning tree when connected according to the described rule.
    The construction begins by invoking this partitionability without proof in the abstract.

pith-pipeline@v0.9.1-grok · 5680 in / 1034 out tokens · 19149 ms · 2026-06-26T06:39:38.618286+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 24 canonical work pages

  1. [1]

    Distributed Computing 1 (1986) https://doi.org/10.1007/BF01660031

    Dally, W., Seitz, C.: The torus routing chip. Distributed Computing 1 (1986) https://doi.org/10.1007/BF01660031

    work page doi:10.1007/bf01660031 1986

  2. [2]

    In: 2018 IEEE International Conference on Cluster Comput- ing (CLUSTER), pp

    Ajima, Y., Kawashima, T., Okamoto, T., Shida, N., Hirai, K., Shimizu, T., Hiramoto, S., Ikeda, Y., Yoshikawa, T., Uchida, K., Inoue, T.: The tofu interconnect d. In: 2018 IEEE International Conference on Cluster Comput- ing (CLUSTER), pp. 646–654 (2018). https://doi.org/10.1109/CLUSTER.2018. 00090

    work page doi:10.1109/cluster.2018 2018

  3. [3]

    Kim, J., Dally, W., Scott, S., Abts, D.: Technology-driven, highly-scalable drag- onfly topology, vol. 36, pp. 77–88 (2008). https://doi.org/10.1109/ISCA.2008. 19

    work page doi:10.1109/isca.2008 2008

  4. [4]

    IEEE Transactions on Parallel and Distributed Systems 21(8), 1132–1142 (2010) https://doi.org/10.1109/TPDS.2009.132

    Flahive, M., Bose, B.: The topology of gaussian and eisenstein-jacobi intercon- nection networks. IEEE Transactions on Parallel and Distributed Systems 21(8), 1132–1142 (2010) https://doi.org/10.1109/TPDS.2009.132

    work page doi:10.1109/tpds.2009.132 2010

  5. [5]

    International 19 Journal of Parallel Programming 34, 193–211 (2006) https://doi.org/10.1007/ s10766-006-0014-1

    Martínez, C., Vallejo, E., Beivide, R., Izu, C., Moretó, M.: Dense gaus- sian networks: Suitable topologies for on-chip multiprocessors. International 19 Journal of Parallel Programming 34, 193–211 (2006) https://doi.org/10.1007/ s10766-006-0014-1

    2006

  6. [6]

    In: Proceedings of the ACM SIGCOMM 2009 Conference on Data Com- munication

    Guo, C., Lu, G., Li, D., Wu, H., Zhang, X., Shi, Y., Tian, C., Zhang, Y., Lu, S.: Bcube: a high performance, server-centric network architecture for modular data centers. In: Proceedings of the ACM SIGCOMM 2009 Conference on Data Com- munication. SIGCOMM ’09, pp. 63–74. Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145...

    work page doi:10.1145/1592568.1592577 2009

  7. [7]

    IEEE Transactions on Computers 44(8), 1021–1030 (1995) https://doi.org/10.1109/12.403718

    Bose, B., Broeg, B., Kwon, Y., Ashir, Y.: Lee distance and topological proper- ties of k-ary n-cubes. IEEE Transactions on Computers 44(8), 1021–1030 (1995) https://doi.org/10.1109/12.403718

    work page doi:10.1109/12.403718 1995

  8. [8]

    Proceedings of the IEEE 77(12), 1829–1841 (1989) https://doi.org/10.1109/5.48826

    Hayes, J.P., Mudge, T.: Hypercube supercomputers. Proceedings of the IEEE 77(12), 1829–1841 (1989) https://doi.org/10.1109/5.48826

    work page doi:10.1109/5.48826 1989

  9. [9]

    60–60 (2002)

    Adiga, N.R., Almasi, G., Almasi, G.S., Aridor, Y., Barik, R., Beece, D., Bellofatto, R., Bhanot, G., Bickford, R., Blumrich, M., Bright, A.A., Brunheroto, J., Cascaval, C., Castanos, J., Chan, W., Ceze, L., Coteus, P., Chatterjee, S., Chen, D., Yates, K.: An overview of the bluegene/l supercomputer, pp. 60–60 (2002). https://doi.org/10.1109/SC.2002.10017

    work page doi:10.1109/sc.2002.10017 2002

  10. [10]

    In: 2020 IEEE Asian Solid-State Circuits Conference (A-SSCC), pp

    Shimizu, T.: Supercomputer fugaku: Co-designed with application developers/re- searchers. In: 2020 IEEE Asian Solid-State Circuits Conference (A-SSCC), pp. 1–4 (2020). https://doi.org/10.1109/A-SSCC48613.2020.9336127

    work page doi:10.1109/a-sscc48613.2020.9336127 2020

  11. [11]

    http://www

    TOP 500 Supercomputer Sites: TOP 500 Supercomputer Sites. http://www. top500.org. Accessed: August 4, 2024

    2024

  12. [12]

    Atchley, C

    Atchley, S., Zimmer, C., Lange, J., Bernholdt, D., Melesse Vergara, V., Beck, T., Brim, M., Budiardja, R., Chandrasekaran, S., Eisenbach, M., Evans, T., Ezell, M., Frontiere, N., Georgiadou, A., Glenski, J., Grete, P., Hamilton, S., Holmen, J., Huebl, A., Jacobson, D., Joubert, W., Mcmahon, K., Merzari, E., Moore, S., Myers, A., Nichols, S., Oral, S., Pap...

    work page doi:10.1145/3581784.3607089 2023

  13. [13]

    https://www.hpe.com/us/en/ compute/hpc/slingshot-interconnect.html

    HPE: HPE SLINGSHOT INTERCONNECT. https://www.hpe.com/us/en/ compute/hpc/slingshot-interconnect.html. Accessed: August 4, 2024 (2022)

    2024

  14. [14]

    Computers, IEEE Transactions on 57, 1046–1056 (2008) https://doi.org/10.1109/TC.2008.57

    Martínez, C., Beivide, R., Stafford, E., Moreto, M., Gabidulin, E.: Modeling toroidal networks with the gaussian integers. Computers, IEEE Transactions on 57, 1046–1056 (2008) https://doi.org/10.1109/TC.2008.57

    work page doi:10.1109/tc.2008.57 2008

  15. [15]

    IEEE Transactions on Network Science and Engineering 9(2), 932–946 (2022)

    Pai, K.-J., Yang, J.-S., Chen, G.-Y., Chang, J.-M.: Configuring protection routing 20 via completely independent spanning trees in dense gaussian on-chip networks. IEEE Transactions on Network Science and Engineering 9(2), 932–946 (2022)

    2022

  16. [16]

    Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2004)

    Dally, W.J., Towles, B.P.: Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2004)

    2004

  17. [17]

    One-to-many node-disjoint paths routing in dense Gaussian networks,

    Alsaleh, O., Bose, B., Hamdaoui, B.: One-to-many node-disjoint paths routing in dense gaussian networks. The Computer Journal 58(2), 173–187 (2015) https: //doi.org/10.1093/comjnl/bxt142

    work page doi:10.1093/comjnl/bxt142 2015

  18. [18]

    IEEE Transactions on Computers 62(10), 1959–1971 (2013) https:// doi.org/10.1109/TC.2012.126

    Zhang, Z., Guo, Z., Yang, Y.: Efficient all-to-all broadcast in gaussian on-chip networks. IEEE Transactions on Computers 62(10), 1959–1971 (2013) https:// doi.org/10.1109/TC.2012.126

    work page doi:10.1109/tc.2012.126 1959

  19. [19]

    IEEE Transactions on Parallel and Distributed Systems 26(4), 1085–1095 (2015) https: //doi.org/10.1109/TPDS.2014.2314689

    Touzene, A.: On all-to-all broadcast in dense gaussian network on-chip. IEEE Transactions on Parallel and Distributed Systems 26(4), 1085–1095 (2015) https: //doi.org/10.1109/TPDS.2014.2314689

    work page doi:10.1109/tpds.2014.2314689 2015

  20. [20]

    In: 2014 IEEE International Parallel and Distributed Processing Symposium Workshops, pp

    Shamaei, A., Bose, B., Flahive, M.: Higher dimensional gaussian networks. In: 2014 IEEE International Parallel and Distributed Processing Symposium Workshops, pp. 1438–1447 (2014). https://doi.org/10.1109/IPDPSW.2014.161

    work page doi:10.1109/ipdpsw.2014.161 2014

  21. [21]

    Journal of Parallel and Distributed Computing 109, 324–332 (2017) https://doi.org/10.1016/j.jpdc.2017.06.018

    Hussain, Z., AlBdaiwi, B., Cerny, A.: Node-independent spanning trees in gaus- sian networks. Journal of Parallel and Distributed Computing 109, 324–332 (2017) https://doi.org/10.1016/j.jpdc.2017.06.018

    work page doi:10.1016/j.jpdc.2017.06.018 2017

  22. [22]

    Applied Mathemat- ics and Computation 268, 489–495 (2015) https://doi.org/10.1016/j.amc.2015

    Chang, Y.-H., Yang, J.-S., Chang, J.-M., Wang, Y.-L.: A fast parallel algorithm for constructing independent spanning trees on parity cubes. Applied Mathemat- ics and Computation 268, 489–495 (2015) https://doi.org/10.1016/j.amc.2015. 06.081

    work page doi:10.1016/j.amc.2015 2015

  23. [23]

    : A fully parallelized scheme of constructing independent spanning trees on möbius cubes

    Yang, J., Wu, M., Chang, J., et al. : A fully parallelized scheme of constructing independent spanning trees on möbius cubes. The Journal of Supercomputing 71, 952–965 (2015) https://doi.org/10.1007/s11227-014-1346-z

    work page doi:10.1007/s11227-014-1346-z 2015

  24. [24]

    IEEE Transactions on Computers 45(2), 174–185 (1996) https://doi.org/10.1109/12.485370

    Fragopoulou, P., Akl, S.G.: Edge-disjoint spanning trees on the star network with applications to fault tolerance. IEEE Transactions on Computers 45(2), 174–185 (1996) https://doi.org/10.1109/12.485370

    work page doi:10.1109/12.485370 1996

  25. [25]

    The Journal of Supercomputing 72(12), 4718–4736 (2016) https://doi.org/10.1007/s11227-016-1768-x

    AlBdaiwi, B., Hussain, Z., Cerny, A., Aldred, R.: Edge-disjoint node-independent spanning trees in dense gaussian networks. The Journal of Supercomputing 72(12), 4718–4736 (2016) https://doi.org/10.1007/s11227-016-1768-x

    work page doi:10.1007/s11227-016-1768-x 2016

  26. [26]

    Discrete Mathematics 234(1), 149–157 (2001) https://doi.org/ 10.1016/S0012-365X(00)00377-0 21

    Hasunuma, T.: Completely independent spanning trees in the underlying graph of a line digraph. Discrete Mathematics 234(1), 149–157 (2001) https://doi.org/ 10.1016/S0012-365X(00)00377-0 21

    work page doi:10.1016/s0012-365x(00)00377-0 2001

  27. [27]

    In: Goos, G., Hartmanis, J., Leeuwen, J., Kučera, L

    Hasunuma, T.: Completely independent spanning trees in maximal planar graphs. In: Goos, G., Hartmanis, J., Leeuwen, J., Kučera, L. (eds.) Graph-Theoretic Concepts in Computer Science. WG 2002. Lecture Notes in Computer Science. Lecture Notes in Computer Science, vol. 2573, pp. 228–241. Springer, ??? (2002). https://doi.org/10.1007/3-540-36379-3_21

    work page doi:10.1007/3-540-36379-3_21 2002

  28. [28]

    In: 2017 IEEE 13th International Conference on Wireless and Mobile Computing, Net- working and Communications (WiMob), pp

    Moinet, A., Darties, B., Gastineau, N., Baril, J.-L., Togni, O.: Completely inde- pendent spanning trees for enhancing the robustness in ad-hoc networks. In: 2017 IEEE 13th International Conference on Wireless and Mobile Computing, Net- working and Communications (WiMob), pp. 63–70 (2017). https://doi.org/10. 1109/WiMOB.2017.8115791

    arXiv 2017

  29. [29]

    IEEE Transactions on Computers 71(5), 1194–1203 (2022) https://doi.org/10.1109/ TC.2021.3077587

    Wang, Y., Cheng, B., Qian, Y., Wang, D.: Constructing completely indepen- dent spanning trees in a family of line-graph-based data center networks. IEEE Transactions on Computers 71(5), 1194–1203 (2022) https://doi.org/10.1109/ TC.2021.3077587

    arXiv 2022

  30. [30]

    IEEE Transactions on Parallel and Distributed Systems 32(3), 665–673 (2021) https://doi.org/10.1109/ TPDS.2020.3029654

    Chen, G., Cheng, B., Wang, D.: Constructing completely independent spanning trees in data center network based on augmented cube. IEEE Transactions on Parallel and Distributed Systems 32(3), 665–673 (2021) https://doi.org/10.1109/ TPDS.2020.3029654

    arXiv 2021

  31. [31]

    IEEE Transactions on Parallel and Distributed Systems 33(8), 1939–1952 (2022) https://doi.org/10.1109/TPDS.2021.3133595

    Li, X.-Y., Lin, W., Liu, X., Lin, C.-K., Pai, K.-J., Chang, J.-M.: Completely independent spanning trees on bccc data center networks with an application to fault-tolerant routing. IEEE Transactions on Parallel and Distributed Systems 33(8), 1939–1952 (2022) https://doi.org/10.1109/TPDS.2021.3133595

    work page doi:10.1109/tpds.2021.3133595 1939

  32. [32]

    Pai, K.-J., Chang, R.-S., Wu, R.-Y., Chang, J.-M.: Three completely independent spanning trees of crossed cubes with application to secure-protection routing. In: 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and ...

    work page doi:10.1109/hpcc/smartcity/ 2019

  33. [33]

    Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States) (2008) 22

    Hagberg, A., Swart, P.J., Schult, D.A.: Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States) (2008) 22

    2008