11 - minimum weight spanning trees Flashcards
What is the minimum spanning tree problem?
Given a weighted, undirected, connected g graph G, compute minimum weighted spanning tree in an asychronous distributed way
spanning tree has n-1 edges
Explain the basic principle of Boruvka’s algorithm.
Each node connects to the nearest other node. Then each fragment connects to the nearest other fragment. this continues untill the MST is constructed
What is the biggest drawback of Boruvka’s algorithm?
This is a centralized,
synchronous algorithm
for a complete network
What are the two types of connections (in Boruvka’s)
- mutual preference: fragments/nodes mutually agree they’re closes
- unilateral preference: one fragment is closer to the other, but not vice-versa
What is the main assumption of MSTs? and why is this needed?
Assume all weights are different. This ensures that there is a unique MST (only one single best awnser!) This is crucial for asynchronous MST problem.
Explain what a MOE is
Minimum-weight Outgoing Edge: is the minimum weighted outgoing edge of a fragment.
(An outgoing edge is any edge that connects a node inside a fragment with a node outside that same fragment.)
Explain the implication of MOE’s.
If F is a fragment and edge e is its MOE, then F with e and the node connected with e not in F (node P) is also a fragment
A fragment is a subtree of the MST. So basically the MOE is also part of the MST
Explain the global idea of the GHS algorithm.
Fragements try to find their MOE and then fuse with the fragements of the incedent node of that MOE.
In case both fragments have the same level, then they merge.
Otherwise the larger leveled fragment will absorb the other one.
Explain what happens to the level, core and the name when two fragments merge using GHS.
Merging means that both fragements were of equal level, so the resulting level is L+1. The MOE over which was merged will become the new core and the name of the new fragment will be the weight of the core (MOE).
Explain what happens to the level, core and the name when a fragment is Absorbed using GHS.
Absorbing means that one fragement had a higher level level, so the resulting level is equal to the fragment that absorbs. The core will remain the same for the higher-leveled core, and so will the name.
The reason for this is that the MOE might not be the same for both fragments, resulting in a tripple fusion. So the core most likely to stay in the middle of the larger level.
Explain the messages the happen when a fragment searches for the MOE. (GHS)
The core sends out initial messages to all other nodes in the fragment. These nodes will try any non-confirmed edges with a test message. These messages are rejected if the link connects to the same fragment, or accepted if they belong to a different fragment. Once a node has tested all its edges, it returns a report message to the core.
Explain the messages inside a fragment after MOE has been established.
There are two options with the same outcome:
1. Either we are going to merge
2. Or we are being absorbed
Both situations are completed by sending a* change_root* allong the MOE path. The leave-node will turn this signal into a connect, which it sends across the MOE.
The other fragment will either identify itself of being higher level, and send an initial_message containing the details of the higher level fragment. In case of an merge, the response is another connect message, followed with the upgradedinitial message containing new core and message.
What is the reaction of a test message from a higher level Fragment? And what is the consquence?
The other node/fragment postpones a reply, as only small fragments can initiate an absorbtion. The consequence is that an higher level fragment is halted untill that test has gotten a response. This gives the lower level fragment a chance to grow to the same level before replying.
Eventually the reply is either an accept or reject, like the normal flow.
Explain how the response of a test message on a MST edge can still be rejected?
In the specific case that a high level fragment wants to test with an low level fragment it sends a test message. This message is postponed. In the meanwhile, the low level message can conclude that it’s MOE is allong that edge, and sends a connect. To which it is absorbed by the higher level fragment. Then the test message is finally resumed, which now is rejected because they are in the same fragment now.
How is eventually the root node decided of the MST when using GHS?
Out of the two nodes connected to the core, the one with the higher id is elected as root.
