Distributed minimum spanning tree

The distributed minimum spanning tree (MST) problem involves the construction of a <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> by a <a href="/facts/Distributed_algorithm/S35ydYjK">distributed algorithm</a>, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles <a href="/facts/Bor%C5%AFvka%27s_algorithm/Hs1pkNRB">Borůvka's algorithm</a>. One important application of this problem is to find a tree that can be used for <a href="/facts/Broadcasting_(computing)/NRj7gHre">broadcasting</a>. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
The problem was first suggested and solved in 
 
 
 
 O
 (
 V
 log
 ⁡
 V
 )
 
 
 {\displaystyle O(V\log V)}
 
 time in 1983 by Gallager et al., where 
 
 
 
 V
 
 
 {\displaystyle V}
 
 is the number of vertices in the <a href="/facts/Graph_theory/VVPCd4TX">graph</a>. Later, the solution was improved to 
 
 
 
 O
 (
 V
 )
 
 
 {\displaystyle O(V)}
 
 and finally

O
 (
 
 
 V
 
 
 
 log
 
 ∗
 
 
 ⁡
 V
 +
 D
 )
 
 
 {\displaystyle O({\sqrt {V}}\log ^{*}V+D)}
 
 where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be

Ω
        
          (
          
            
              
                
                  V
                
                
                  log
                  ⁡
                  V
                
              
            
            +
            D
          
          )
        
        .
      
    
    {\displaystyle \Omega \left({{\frac {\sqrt {V}}{\log V}}+D}\right).}

Distributed minimum spanning tree open-in-new

Distributed minimum spanning tree