{"history":[],"article":{"id":"159f209d-608b-4bb3-bee0-c6d0a2a25ace","title":"Distributed minimum spanning tree","slug":"distributed-minimum-spanning-tree","content":":::summary\n:::\n\n# \nThe **distributed [minimum spanning tree](https://bliptext.com/articles/minimum-spanning-tree) (MST)** problem involves the construction of a [minimum spanning tree](https://bliptext.com/articles/minimum-spanning-tree) by a [distributed algorithm](https://bliptext.com/articles/distributed-algorithm), in a network where nodes communicate by message passing.\nIt is radically different from the classical sequential problem, although the most basic approach resembles [Borůvka's algorithm](https://bliptext.com/articles/bor-vka-s-algorithm).\nOne important application of this problem is to find a tree that can be used for [broadcasting](https://bliptext.com/articles/broadcasting-computing).\nIn 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.\nThe problem was first suggested and solved in O(V \\log V) time in 1983 by Gallager et al., where V is the number of vertices in the [graph](https://bliptext.com/articles/graph-theory).\nLater, the solution was improved to O(V) and finally\nwhere D is the network, or graph diameter.\nA lower bound on the time complexity of the solution has been eventually shown to be\n# [Example of a MST: The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. | upload.wikimedia.org/wikipedia/commons/d/d2/Minimum///spanning///tree.svg]\n\n# Overview\nThe input graph G(V,E) is considered to be a network, where vertices V are independent computing nodes and edges E are communication links.\nLinks are weighted as in the classical problem.\nAt the beginning of the algorithm, nodes know only the weights of the links which are connected to them.\n(It is possible to consider models in which they know more, for example their neighbors' links.)\nAs the output of the algorithm, every node knows which of its links belong to the minimum spanning tree and which do not.\n\n# MST in message-passing model\nThe [message-passing](https://bliptext.com/articles/message-passing) model is one of the most commonly used models in [distributed computing](https://bliptext.com/articles/distributed-computing).\nIn this model, each process is modeled as a node of a graph.\nEach communication channel between two processes is an edge of the graph.\nTwo commonly used algorithms for the classical minimum spanning tree problem are [Prim's algorithm](https://bliptext.com/articles/prim-s-algorithm) and [Kruskal's algorithm](https://bliptext.com/articles/kruskal-s-algorithm).\nHowever, it is difficult to apply these two algorithms in the distributed message-passing model.\nThe main challenges are:\nDue to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model.\nSome bear similarities to [Borůvka's algorithm](https://bliptext.com/articles/bor-vka-s-algorithm) for the classical MST problem.\n\n# GHS algorithm\nThe GHS algorithm of [Gallager](https://bliptext.com/articles/robert-g-gallager), Humblet and Spira is one of the best-known algorithms in distributed computing theory.\nThis algorithm constructs an MST in the asynchronous message-passing model.\n\n## Assumptions\nThe GHS algorithm requires several assumptions.\n\n## Properties of MSTs\nDefine a fragment of an MST T to be a sub-tree of T. That is, a fragment is a connected set of nodes and edges of T. MSTs have two important properties in relation to fragments:\nThese two properties form the basis for proving correctness of the GHS algorithm.\nIn general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment, and then joining fragments until a single fragment is left.\nThe above properties imply that the remaining fragment must be an MST.\n\n## Description of the algorithm\nThe GHS algorithm assigns a level to each fragment, which is a non-decreasing integer with initial value 0.\nFurthermore, each fragment with a non-zero level has an ID, which is the ID of the core edge in the fragment, which is selected when the fragment is constructed.\nDuring the execution of the algorithm, each node can classify each of its incident edges into three categories:\nIn level-0 fragments, each awakened node will do the following:\nThe edge that is chosen by the two nodes it connects becomes the core edge, and is assigned level 1.\nIn non-zero-level fragments, a separate algorithm is executed in each level.\nThis algorithm can be separated into three stages: broadcast, convergecast, and change core.\n\n### Broadcast\nThe two nodes adjacent to the core broadcast messages to the rest of the nodes in the fragment.\nThe messages are sent via the branch edge but not via the core.\nEach broadcast message contains the ID and level of the fragment.\nAt the end of this stage, each node has received the new fragment ID and level.\n\n### Convergecast\nIn this stage, all nodes in the fragment cooperate to find the minimum weight outgoing edge of the fragment.\nOutgoing edges are edges connecting to other fragments.\nThe messages sent in this stage are in the opposite direction of the broadcast stage.\nInitialized by all the leaves (the nodes that have only one branch edge), a message is sent through the branch edge.\nThe message contains the minimum weight of the incident outgoing edge it found (or infinity if no such edge was found).\nThe way to find the minimum outgoing edge will be discussed later.\nFor each non-leaf node, given the number of its branch edges as n, after receiving n - 1 convergecast messages, it will pick the minimum weight from the messages and compare it to the weights of its incident outgoing edges.\nThe smallest weight will be sent toward the branch it received the broadcast from.\n\n### Change core\nAfter the completion of the previous stage, the two nodes connected by the core can inform each other of the best edges they received.\nThen they can identify the minimum outgoing edge from the entire fragment.\nA message will be sent from the core to the minimum outgoing edge via a path of branch edges.\nFinally, a message will be sent out via the chosen outgoing edge to request to combine the two fragments that the edge connects.\nDepending on the levels of those two fragments, one of two combined operations are performed to form a new fragment; details discussed below.\n\n### Finding the minimum-weight incident outgoing edge\nAs discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core.\nIf node n receives a broadcast, it will pick its minimum weight basic edge and send a message to the node n' on the other side with its fragment's ID and level.\nThen, node n' will decide whether the edge is an outgoing edge and send back a message to notify node n of the result.\nThe decision is made according to the following:\n\n### Combining two fragments\nLet F and F' be the two fragments that need to be combined.\nThere are two ways to do this:\nFurthermore, when an \"Absorb\" operation occurs, F must be in the stage of changing the core, while F' can be in an arbitrary stage.\nTherefore, \"Absorb\" operations may be done differently depending on the state of F'.\nLet e be the edge that F and F' want to combine with, and let n and n' be the two nodes connected by e in F and F', respectively.\nThere are two cases to consider:\n

\nNode n' has received broadcast message but it has not sent a convergecast message back to the core.\nIn this case, fragment F can simply join the broadcast process of F'.\nSpecifically, we image F and F' have already combined to form a new fragment F, so we want to find the minimum weight outgoing edge of F.\nIn order to do that, node n' can initiate a broadcast to F to update the fragment ID of each node in F and collect minimum weight outgoing edge in F.
\nNode n' has already sent a convergecast message back to the core.\nBefore node n' sent a convergecast message, it must have picked a minimum weight outgoing edge.\nAs we discussed above, n' does that by choosing its minimum weight basic edge, sending a test message to the other side of the chosen edge, and waiting for the response.\nSuppose e' is the chosen edge, we can conclude the following:\n
1. e' \\neq e
\nThe second statement follows if the first one holds.\nFor the first statement, suppose n' chose the edge e and sent a test message to n via edge e. Then, node n will delay the response (according to case 3 of \"Finding the minimum weight incident outgoing edge\").\nThen, it is impossible that n' has already sent its convergecast message.\nBy the aforementioned conclusions 1 and 2, we can conclude it is safe to absorb F into F' since e' is still the minimum outgoing edge to report after F is absorbed.\n

\n\n### Maximum number of levels\nAs mentioned above, fragments are combined by either \"Merge\" or \"Absorb\" operation.\nThe \"Absorb\" operation does not change the maximum level among all fragments.\nThe \"Merge\" operation may increase the maximum level by 1.\nIn the worst case, all fragments are combined with \"Merge\" operations, so the number of fragments decreases by half in each level.\nTherefore, the maximum number of levels is O(\\log V), where V is the number of nodes.\n\n## Progress property\nThe GHS algorithm has a nice property that the lowest level fragments will not be blocked, although some operations in the non-lowest level fragments may be blocked.\nThis property implies the algorithm will eventually terminate with a minimum spanning tree.\n\n# Approximation algorithms\nAn O(\\log n)-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.\nThis algorithm runs in time, where L is the local shortest path diameter of the graph.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T08:10:44.805Z","updated_at":"2025-01-26T08:10:44.805Z","search_vector":"'distribut':1 'minimum':2 'span':3 'tree':4","search_content":" \n \n\n# \nThe **distributed [minimum spanning tree](https://bliptext.com/articles/minimum-spanning-tree) (MST)** problem involves the construction of a [minimum spanning tree](https://bliptext.com/articles/minimum-spanning-tree) by a [distributed algorithm](https://bliptext.com/articles/distributed-algorithm), in a network where nodes communicate by message passing.\nIt is radically different from the classical sequential problem, although the most basic approach resembles [Borůvka's algorithm](https://bliptext.com/articles/bor-vka-s-algorithm).\nOne important application of this problem is to find a tree that can be used for [broadcasting](https://bliptext.com/articles/broadcasting-computing).\nIn 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.\nThe problem was first suggested and solved in O(V \\log V) time in 1983 by Gallager et al., where V is the number of vertices in the [graph](https://bliptext.com/articles/graph-theory).\nLater, the solution was improved to O(V) and finally\nwhere D is the network, or graph diameter.\nA lower bound on the time complexity of the solution has been eventually shown to be\n# [Example of a MST: The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. | upload.wikimedia.org/wikipedia/commons/d/d2/Minimum///spanning///tree.svg]\n\n# Overview\nThe input graph G(V,E) is considered to be a network, where vertices V are independent computing nodes and edges E are communication links.\nLinks are weighted as in the classical problem.\nAt the beginning of the algorithm, nodes know only the weights of the links which are connected to them.\n(It is possible to consider models in which they know more, for example their neighbors' links.)\nAs the output of the algorithm, every node knows which of its links belong to the minimum spanning tree and which do not.\n\n# MST in message-passing model\nThe [message-passing](https://bliptext.com/articles/message-passing) model is one of the most commonly used models in [distributed computing](https://bliptext.com/articles/distributed-computing).\nIn this model, each process is modeled as a node of a graph.\nEach communication channel between two processes is an edge of the graph.\nTwo commonly used algorithms for the classical minimum spanning tree problem are [Prim's algorithm](https://bliptext.com/articles/prim-s-algorithm) and [Kruskal's algorithm](https://bliptext.com/articles/kruskal-s-algorithm).\nHowever, it is difficult to apply these two algorithms in the distributed message-passing model.\nThe main challenges are:\nDue to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model.\nSome bear similarities to [Borůvka's algorithm](https://bliptext.com/articles/bor-vka-s-algorithm) for the classical MST problem.\n\n# GHS algorithm\nThe GHS algorithm of [Gallager](https://bliptext.com/articles/robert-g-gallager), Humblet and Spira is one of the best-known algorithms in distributed computing theory.\nThis algorithm constructs an MST in the asynchronous message-passing model.\n\n## Assumptions\nThe GHS algorithm requires several assumptions.\n\n## Properties of MSTs\nDefine a fragment of an MST T to be a sub-tree of T. That is, a fragment is a connected set of nodes and edges of T. MSTs have two important properties in relation to fragments:\nThese two properties form the basis for proving correctness of the GHS algorithm.\nIn general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment, and then joining fragments until a single fragment is left.\nThe above properties imply that the remaining fragment must be an MST.\n\n## Description of the algorithm\nThe GHS algorithm assigns a level to each fragment, which is a non-decreasing integer with initial value 0.\nFurthermore, each fragment with a non-zero level has an ID, which is the ID of the core edge in the fragment, which is selected when the fragment is constructed.\nDuring the execution of the algorithm, each node can classify each of its incident edges into three categories:\nIn level-0 fragments, each awakened node will do the following:\nThe edge that is chosen by the two nodes it connects becomes the core edge, and is assigned level 1.\nIn non-zero-level fragments, a separate algorithm is executed in each level.\nThis algorithm can be separated into three stages: broadcast, convergecast, and change core.\n\n### Broadcast\nThe two nodes adjacent to the core broadcast messages to the rest of the nodes in the fragment.\nThe messages are sent via the branch edge but not via the core.\nEach broadcast message contains the ID and level of the fragment.\nAt the end of this stage, each node has received the new fragment ID and level.\n\n### Convergecast\nIn this stage, all nodes in the fragment cooperate to find the minimum weight outgoing edge of the fragment.\nOutgoing edges are edges connecting to other fragments.\nThe messages sent in this stage are in the opposite direction of the broadcast stage.\nInitialized by all the leaves (the nodes that have only one branch edge), a message is sent through the branch edge.\nThe message contains the minimum weight of the incident outgoing edge it found (or infinity if no such edge was found).\nThe way to find the minimum outgoing edge will be discussed later.\nFor each non-leaf node, given the number of its branch edges as n, after receiving n - 1 convergecast messages, it will pick the minimum weight from the messages and compare it to the weights of its incident outgoing edges.\nThe smallest weight will be sent toward the branch it received the broadcast from.\n\n### Change core\nAfter the completion of the previous stage, the two nodes connected by the core can inform each other of the best edges they received.\nThen they can identify the minimum outgoing edge from the entire fragment.\nA message will be sent from the core to the minimum outgoing edge via a path of branch edges.\nFinally, a message will be sent out via the chosen outgoing edge to request to combine the two fragments that the edge connects.\nDepending on the levels of those two fragments, one of two combined operations are performed to form a new fragment; details discussed below.\n\n### Finding the minimum-weight incident outgoing edge\nAs discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core.\nIf node n receives a broadcast, it will pick its minimum weight basic edge and send a message to the node n' on the other side with its fragment's ID and level.\nThen, node n' will decide whether the edge is an outgoing edge and send back a message to notify node n of the result.\nThe decision is made according to the following:\n\n### Combining two fragments\nLet F and F' be the two fragments that need to be combined.\nThere are two ways to do this:\nFurthermore, when an \"Absorb\" operation occurs, F must be in the stage of changing the core, while F' can be in an arbitrary stage.\nTherefore, \"Absorb\" operations may be done differently depending on the state of F'.\nLet e be the edge that F and F' want to combine with, and let n and n' be the two nodes connected by e in F and F', respectively.\nThere are two cases to consider:\n \nNode n' has received broadcast message but it has not sent a convergecast message back to the core.\nIn this case, fragment F can simply join the broadcast process of F'.\nSpecifically, we image F and F' have already combined to form a new fragment F, so we want to find the minimum weight outgoing edge of F.\nIn order to do that, node n' can initiate a broadcast to F to update the fragment ID of each node in F and collect minimum weight outgoing edge in F. \nNode n' has already sent a convergecast message back to the core.\nBefore node n' sent a convergecast message, it must have picked a minimum weight outgoing edge.\nAs we discussed above, n' does that by choosing its minimum weight basic edge, sending a test message to the other side of the chosen edge, and waiting for the response.\nSuppose e' is the chosen edge, we can conclude the following:\n \n e' \\neq e \n \n \nThe second statement follows if the first one holds.\nFor the first statement, suppose n' chose the edge e and sent a test message to n via edge e. Then, node n will delay the response (according to case 3 of \"Finding the minimum weight incident outgoing edge\").\nThen, it is impossible that n' has already sent its convergecast message.\nBy the aforementioned conclusions 1 and 2, we can conclude it is safe to absorb F into F' since e' is still the minimum outgoing edge to report after F is absorbed.\n \n\n### Maximum number of levels\nAs mentioned above, fragments are combined by either \"Merge\" or \"Absorb\" operation.\nThe \"Absorb\" operation does not change the maximum level among all fragments.\nThe \"Merge\" operation may increase the maximum level by 1.\nIn the worst case, all fragments are combined with \"Merge\" operations, so the number of fragments decreases by half in each level.\nTherefore, the maximum number of levels is O(\\log V), where V is the number of nodes.\n\n## Progress property\nThe GHS algorithm has a nice property that the lowest level fragments will not be blocked, although some operations in the non-lowest level fragments may be blocked.\nThis property implies the algorithm will eventually terminate with a minimum spanning tree.\n\n# Approximation algorithms\nAn O(\\log n)-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.\nThis algorithm runs in time, where L is the local shortest path diameter of the graph.","revisionCount":0},"hasMore":false,"nextCursor":null}

History