Maintaining Minimum Spanning Trees in Dynamic Distributed Networks: Non-Tree-Edge Tracking with Predictive Scheduling

Abstract

Spanning structures that must be maintained, not merely rebuilt, underlie sensor fabrics, peer-to-peer overlays, and software-defined networks. We give a complete treatment of distributed minimum-spanning-tree (MST) construction and maintenance built on non-tree-edge (NTE) tracking, which certifies the edges excluded from the tree rather than growing tree fragments. First, we provide the full specification and correctness proofs of the static NTE algorithm—previously available only in outline—achieving O(m) messages of O(logn) bits in O(d) rounds with only three message types. Second, we prove an exact maintenance algorithm for edge-weight updates: three of four update cases resolve in O(1), and the fourth is resolved by ExactSwap within a message bound that experiments show to be tight (median ratio 1.00); across 221,874 update records, the median affected set is 2, independent of scale (n=500–20,000). Third, we establish a separation result: verifying a replacement edge distributively provably requires examining the entire search region, an obstruction with no centralized analogue. Fourth, we show that prediction is best used for scheduling: under contention, prioritizing predicted-cheap updates improves mean time-to-resolution by 2.1–3.8× over FIFO, matching an oracle, with a linear model sufficing.