## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### Analysis of the AdaptiveLID Algorithm
\(\Box\)  
**Lemma 8**: _The AdaptiveLID algorithm terminates for every node \(i\in V\) after changes complete._  
**Proof:** For the static case, Lemma 5 applies, and the algorithm terminates. For the dynamic case, a change may cause some proposals to be canceled and reissued on nodes at a distance of one or two (Lemma 7). The only cases in which the algorithm may not terminate on these nodes is when they wait indefinitely for a neighbor's answer or their preference list \"oscillates\", with proposals being canceled and reissued on the same neighbors in an alternating way over time. By Lemma 6, we can ignore weight updates, since they complete in a finite amount of time. For the first case, a node can wait indefinitely only if a communication cycle exists: each node \(n_{i\bmod k}\) in a group of nodes, \(\{n_{0},n_{1},\ldots,n_{k-1}\}\), sends a PROP message to node \(n_{(i+1)\mod k}\) and awaits for an answer in order to reply back to node \(n_{(i-1)\mod k}\), that is \(w(n_{i\mod k},n_{(i+1)\mod k})>w(n_{i\mod k},n_{(i-1)\mod k})\). By adding all such equations on the cycle and using properties of the modulo operator, we get:  
\[\sum_{i=0}^{k-1}w\left(n_{i\bmod k},n_{(i+1)\bmod k}\right)>\sum _{i=0}^{k-1}w\left(n_{i\bmod k},n_{(i-1)\bmod k}\right)=\] \[=\sum_{i=0}^{k-1}w\left(n_{(i+1)\bmod k},n_{i\bmod k}\right)= \sum_{i=0}^{k-1}w\left(n_{i\bmod k},n_{(i+1)\bmod k}\right) \tag{32}\]  
which is a contradiction. For the second case, by Lemma 7 and since we assumed that the changes are completed, we have that any potential canceling and reissuing of proposals finishes in a finite amount of time and therefore no oscillations occur. \(\Box\)  
**Lemma 9**: _For every node \(i\) Algorithm AdaptiveLID chooses all locally heaviest edges that are adjacent to it, if there is enough quota \(b_{i}\) available, or otherwise chooses the \(b_{i}\) of those that are heavier than any unchosen one._  
**Proof:** For a static network, Lemma 4 is applicable. For a dynamic network, by Lemma 7, after a finite amount of time, every node \(i\) cancels all proposals to neighbors that are no longer locally heaviest after a change and proposes to the locally heaviest ones. Some of these proposals will result in a match if the receiving node also considers the originating node locally heaviest. The same will happen to all proposed nodes, as long as the originating and receiving nodes have available quotas. If some node lacks in available quota, we know that its matched incident edges are heavier than its unmatched locally heaviest, since by Lemma 7, it would have to cancel the appropriate proposals and issue new ones towards locally heaviest neighbors. \(\Box\)  
**Lemma 10**: _The AdaptiveLID algorithm, when run on a network with changes, produces the same matching with the LID algorithm that is run on the same network after the changes complete._  
Proof. : By Lemma 8, we get that the AdaptiveLID algorithm terminates for every node, and by Lemma 9, we know that at termination, it has chosen only the locally heaviest edges of maximum weight. Since by Lemma 4 the static algorithm also selects the locally heaviest edges of maximum weight at termination, it follows that the two algorithms make the same choices for the same networks.