Content deleted Content added
Kaltenmeyer (talk | contribs) m →Combining two fragments: typo, typo(s) fixed: aformentioned → aforementioned |
Reverted 1 edit by 189.156.187.30 (talk): Rv; removed with no reason |
||
| (9 intermediate revisions by 4 users not shown) | |||
Line 31:
* Each edge in the input graph has distinct finite weights. This assumption is not needed if there is a consistent method to break ties between edge weights.
* Each node initially knows the weight of each edge incident to that node.
* Initially, each node is in an inactive state. Each
* Messages can be transmitted independently in both directions on an edge and arrive after an unpredictable but finite delay, without error.
* Each edge delivers messages in [[FIFO (computing and electronics)|FIFO]] order.
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 ====
| |||