In previous lecture we have discussed the basic concepts of distributed shared memory, it is consistency models and algorithm for shared memory mutual exclusion Content of this lecture in this lecture we will discuss about distributed minimum spanning tree and also discuss the well known GHS algorithm from the following reference Gallager, Humblet, Spira, a distributed algorithm for minimum weight spanning trees in ACM transactions programming language in 1983 Introduction, the distributed minimum spanning tree MST problem involves the construction of a spanning tree by a distributed algorithm of a minimum weight, in a network they are the nodes communicate by passing messages One important application of this problem is to find a tree that can be used for broadcasting In particular, the cost of a message to pass through an edge in a graph is significant and MST can minimize the total cost of for a source process to communicate with all other processes in the network Preliminaries, weighted graph this algorithm requires a weighted graph of n number of vertices and m number of edges where the weights are given to the edges or non negative weights and also the weights are the distinct So, the spanning tree is a tree induced in a graph which is connected acyclic graph spanning all the vertices of G So, we have shown you that the red colored edges forms our tree out of the given graph which we have shown you in the previous slide Now, that spanning tree which is subject to the sum of its weight is minimized is called minimum spanning tree So, for minimum spanning tree the weight of a tree is nothing, but sum of all the edges of that particular tree and it should be the minimum of all possible spanning trees of the minimum weight is called minimum weight spanning tree A spanning tree formation or a construction algorithms in the classical system is well known in the form of Prim’s algorithm and Kruskal’s algorithm But if the system model is the distributed system where the nodes are communicating through the messages and the messages are transmitted with unpredictable delay in a finite predictable time So, in that particular model construction of a minimum spanning tree is going to be a challenging task So, here we are going to see the algorithm of constructing the minimum spanning tree So, minimum spanning tree means minimum weighted spanning tree in a distributed system we are going to see Now we are going to see some of the terminologies which we are going to use in this particular lecture the first of them is a spanning tree fragment So, any connected sub tree of a minimum spanning tree is called the spanning tree fragment So, here you can see here that the sub tree shown as the green edges is called a basically fragment spanning tree fragment Now, the spanning tree fragment will have different edges which are out of that particular tree and connecting to some other fragments are the nodes So, an edge adjacent to the fragment with the smallest weight that does not create a cycle is called minimum weight outgoing edge Take for example, that we have seen this as a fragment, and out of this particular fragment

we can see that these are the edges which are out of this particular fragment Among these edges we can see the edge which is given as the red colored edge is of the minimum weight So, hence the definition says that minimum weight outgoing edge So, the edge nine becomes the minimum weight outgoing edge and which is popularly known as MWOE in this particular algorithm Now, MST fragment a connected sub tree of the minimum spanning tree, so you can see in this example there are different fragments are possible So, minimum spanning tree properties, the first property MST property 1 says that given a fragment of an MST let e be a minimum weight outgoing edge of a fragment then joining e and its adjacent non fragment node to a fragment yields another fragment of an minimum spanning tree Take this particular example that this is a fragment with one minimum weight outgoing edge which is shown as e So, here we can see out of this animation that when then joining e and its adjacent, adjacent non fragment node to the fragment yields another fragment of a MST which is shown over here Now, MST property 2 says that if all the edges of a connected graph have different weights then the MST is unique So, here in this animation we can see that in this particular tree let us take an edge e prime and in this particular spanning tree on that particular graph another spanning tree that is T with another e and in that edge is e Now we can see that let e be the minimal weight edge not in both MST without loss of generality e is in T. Now, at least with e as a cycle Now, at least cycle edge e prime is not in T since weight of e is less than weight of e prime we conclude that T prime with e and without e prime is a smaller MST then T prime So, basically this particular animation proof shows that if all the edges of the connected graph have different weights then MST is a unique So, with these two properties the idea of MST based on these two properties we can see that we have to start with the fragment of a singleton node as shown over here Now, the next step is to enlarge the fragment in any order by using property 1 and combine fragments with a common node So, that is property number 2 So, in this process; that means, applying iteratively property 1 and 2 we will get the complete coverage and will get the MST; that means, the fragment is continuously going using property 1 and 2 till it covers as one fragment and that is a minimum weighted spanning tree So, minimum spanning tree in a message passing model the message passing model is one of the most commonly used model in the distributed computing in this model each process modeled as a node in a graph the communication channel between two processes is an edge of the graph Two commonly used algorithms for classical minimum spanning tree problem are Prim’s algorithm and Kruskal’s algorithm; however, it is difficult to apply these two algorithms in a distributed message passing model The main challenges are both Prim’s algorithm and Kruskal’s algorithm require processing one node or a vertex at a time, making it difficult to make them run in parallel Both Prim’s algorithm and Kruskal’s algorithm require processes to know the state of the whole graph which is very difficult to discover in the message passing model due to these

difficulties new techniques were needed for designing the distributed algorithms for minimum spanning tree in this problem setting that is in the minimum in the message passing model GHS algorithm, GHS algorithm of Gallager Humblet and Spira 1983 is one of the best known algorithms in distributed computing theory GHS is a distributed algorithm based on Kruskal’s algorithm that constructs the minimum weight spanning tree in a connected undirected graph with distinct edge weights A processor exists at each node of a graph knowing initially only the weights of the adjacent edges the processor will be the same algorithm and exchange messages with the neighbors until tree is constructed This algorithm can construct the minimum spanning tree in asynchronous message passing model GHS algorithm can run in synchronous as well as in asynchronous mode of communication and computation, in synchronous GHS it works with non uniform model with a distinct weight steps first initially each node is a fragment repeat in parallel synchronous phase each fragment coordinated by the fragment root node finds its minimum weight outgoing edge merge the fragment adjacent to minimum weight outgoing edge until there is only one fragment In asynchronous GHS it simulates the synchronous version works with both uniform and distinct weights uniform models distinct weights So, steps in asynchronous GHS every fragment f has the level which is greater than 0 or equal to 0 at the beginning each node is a fragment of level 0, two types of merges absorption and join Overview the input graph is considered to be the network and links are basically given weights is as in the classical problem Edges represents the communication links at the beginning of the algorithm nodes know only the weights of the links which are connected to them As the output of the algorithm every nodes knows which of its links belongs to the minimum spanning tree and which do not Preconditions the algorithm should run on a connected undirected graph the algorithm should have distinct finite weights assigned to each edge, each node initially knows the weight of weight for each edge incident to that node Initially each node is in a quiescent state and it is either spontaneously awakens or awakened by receipt of any message from another node Messages can be transmitted independently in both the directions on an edge and arrive after an unpredictable, but finite delay without error Each edge delivers message in FIFO order The idea of distributed MST, GHS notations first fragment is every node start with a single fragment Each fragment finds its minimum outgoing edge then it tries to combine with the adjacent fragment every fragment has an associated level that That has impact on combining fragments a fragment with a single node is defined to be a level 0 The combination of two fragments depend on the level of fragments So, if the fragment F wishes to connect to a fragment F prime this is F and this is F prime and the level of fragment F is L is less than the level of f prime then F is absorbed in F prime and the resulting fragment is at the level L prime that is shown over here So, the resulting fragment will be F prime and its level will be the same as F primes level that is L prime is equal to 2 Now, if the fragments F and F prime have the same minimum outgoing edge and L is equal to L prime that is their levels are same Then the fragments combine into a new fragment F double prime and the level of this new fragment will be plus 1 of the earlier fragments which were seen as L. So, it will become L plus

1 Now if the fragments f and f prime with the same level were combined then combined edge is called the core of the new segment So, here you can see that the core this is the core why because this was instrumental in combining the two fragments F and F prime, it becomes the core of the new segment Then in GHS notation next thing is about node states, state each node has a state there are three states in which the node will be at a particular instant of time that is the sleeping state is initial state find state means during the fragment search for a minimal outgoing edge found means otherwise when a minimal outgoing edge was found So, sleeping find found So, there are three different node states The algorithm description of the algorithm that GHS algorithm assigns a level to each fragment which is a non decreasing integer with the initial value 0, each nonzero level fragment has an ID which is the ID of the core edge in the fragment which is selected when the fragments is constructed during the execution of the algorithm each node can classify each of its incident edges into three categories that is the branch edges is the first category are those that have already been determined to be a part of MST The second type of edges rejected edge are those edge that have been already determined not to be a part of MST Third is the basic edge are neither branches nor the rejected edge So, the description of algorithm for level 0 fragments each awakened node will do the following First choose its minimum weight incident edge and marks that edge as the branch edge, send a message via the branches to notify the node on the other side wait for the message from the others end of the edge The edge chosen by both the nodes it connects becomes the core with level 1 For nonzero level fragment and execution of the algorithm can be separated into three stages in each level – first is broadcast the two nodes adjacent to the core broadcast messages to the rest of the nodes in the fragment the messages are sent via the branch Edge not via the core each broadcast message contains the ID and the level of the fragment at the end of this stage each node has received the new fragment ID and the level Converge cast at this stage all nodes in the fragment cooperate to find the minimum weight outgoing edge of the fragment; outgoing edges are the edges connecting to other fragment The messages sent in this stage are in the opposite direction of the broadcast stage initialized by all the leaves the nodes that have only one branch edge a message is sent through the branch edge The message contains the minimum weight of the incident outgoing edge it found For each non leaf node let the number of its branch edges are branch edges be n after receiving n minus 1 converge cast messages it will pick the minimum weight from the messages and compare it to the weight of its incident outgoing edges the smallest weight will be sent towards the branch it received the broadcast from Change core after the completion of the initial stage the two nodes connected by the core can inform each other of the best edge they received then they can identify the minimum outgoing edge from entire fragment A message will be sent from the core to the minimum outgoing edge via path of the branch edges Finally, a message will be sent out via choosing via chosen outgoing edge to request to combine the two fragments that the edge connects So, that was a brief overview of the algorithm Now, let us see the execution how these steps are basically incorporated in the execution of the algorithm So, in this particular execution example the fragment with a minimum outgoing edge discovery is shown that is special case of 0 level fragments they are sleeping when a node awakens from

the sleeping state finds a minimum edge connected Marks it as a branch of the MST and sends a connect message over this edge, goes into a found state So, we have seen that the node is making a transition from sleeping to find to or found three states of the process and also send a message that connector over minimum weight outgoing edge which is shown as the red color over here Now this particular correct message will try to combine the fragments So, take a fragment at level l that just combined out of the two level L minus 1 fragment the weight of the core is the identity of the fragment it acts as the root of the fragment tree So, the nodes adjacent to the core send an initiate message to the borders, relayed by the intermediate nodes in the fragment puts the node in the find state So, the basic edges yet to be classified can be inside the fragment or outgoing edges Rejected will always be inside fragment and branches is an MST edge So, on receiving the initiate message a node tries to find the minimum outgoing edge sends a test message on the basic edge a minimal first On receiving the test message in case of the same identity send a reject message the edge is rejected same identity means in it is in the same fragment, same fragment the connection will lead to a cycle In case the test was sent in both directions the edge is rejected automatically without a reject message In case of self lower level delay the response until the identity rises sufficiently In case such an accept message the edges accepted as the candidate So, the node sent the report messages along the branches of MST, if no outgoing edge was found the algorithm is complete after sending they go in a found state Every leaf sends the report when resolved its outgoing edge And its children send theirs Every node remembers the branch to the minimal outgoing edge of its sub branch denoted the best edge The core adjacent nodes exchange reports and decide on minimal outgoing edge When decided a change-core messages sent over the branches to the minimal outgoing edge the tree branch point to the new core Finally, a connect message is sent over the minimal edge So, when connecting the same level fragments both core adjacent nodes send a connect message which causes the level to be increased, as a result core is changed and new initiate message are sent When lower level fragment f prime at a node n prime joins the same fragment at a node n before n sends its report we can send n prime and initiate message with fine listed, so it joins the search When the lower level fragment F prime at a node n prime joins some fragment f at a node after n sent its report it means that n already found a lower edge and therefore, we can send

n prime an initiate message with the found message So, it does not join the search Forwarding the initiate message at level L when forwarding an initiate message to the leafs, it is also forwarded to any pending fragments at level l minus one as they might be delayed with the response So, we can see that log n is an upper bound on the fragment levels and the connect messages send on the minimal outgoing Edges only and there is no deadlock We have to assume then the communication complexity at each at every, but the 0 or the last levels each node can accept up to 1 initiate accept messages it can transmit up to 1 test report change route connect message Since the number of levels is bounded by log n number of such messages is at most 5 n log n minus 1 At level 0 each node receives at most one initiate and transmit at most one connect at the last level a node can send at most one report message, as a result at most 3N messages So, as a result the upper bound is 5N log to the base 2 N plus 2E So, time under the emission of initial awakening it is 5N log to the base 2 N Conclusion, distributed manual spanning tree algorithms are useful in communication network when one wishes to broadcast information from one node to all other nodes and there is a cost associated with each channel of the network In addition to the broadcast application there are many potential control problems for the network whose communication complexities are reduced by having (Refer Time: 27:13)