Content deleted Content added
→Assumptions: Fixed typo Tags: Mobile edit Mobile web edit |
Afernand74 (talk | contribs) m coding |
||
Line 77:
Furthermore, when an "Absorb" operation occurs, <math>F</math> must be in the stage of changing the core, while <math>F'</math> can be in an arbitrary stage. Therefore, "Absorb" operations may be done differently depending on the state of <math>F'</math>. Let <math>e</math> be the edge that <math>F</math> and <math>F'</math> want to combine with, and let <math>n</math> and <math>n'</math> be the two nodes connected by <math>e</math> in <math>F</math> and <math>F'</math>, respectively. There are two cases to consider:
{{numbered list
| Node <math>n'</math> has received broadcast message but it has not sent a convergecast message back to the core. In this case, fragment <math>F</math> can simply join the broadcast process of <math>F'</math>. Specifically, we image <math>F</math> and <math>F'</math> have already combined to form a new fragment <math>F''</math>, so we want to find the minimum weight outgoing edge of <math>F''</math>. In order to do that, node <math>n'</math> can initiate a broadcast to <math>F</math> to update the fragment ID of each node in <math>F</math> and collect minimum weight outgoing edge in <math>F</math>.
| Node <math>n'</math> has already sent a convergecast message back to the core. Before node <math>n'</math> sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, <math>n'</math> 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. Suppose <math>e'</math> is the chosen edge, we can conclude the following:▼
▲Node <math>n'</math> has already sent a convergecast message back to the core. Before node <math>n'</math> sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, <math>n'</math> 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. Suppose <math>e'</math> is the chosen edge, we can conclude the following:
▲<li><math>e' \neq e</math></li>
▲<li><math>\mathit{weight}(e') < \mathit{weight}(e)</math></li>
The second statement follows if the first one holds. For the first statement, suppose <math>n'</math> chose the edge <math>e</math> and sent a test message to <math>n</math> via edge <math>e</math>. Then, node <math>n</math> will delay the response (according to case 3 of "Finding the minimum weight incident outgoing edge"). Then, it is impossible that <math>n'</math> has already sent its convergecast message. By the aforementioned conclusions 1 and 2, we can conclude it is safe to absorb <math>F</math> into <math>F'</math> since <math>e'</math> is still the minimum outgoing edge to report after <math>F</math> is absorbed.
}}
==== Maximum number of levels ====
| |||