## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### Analysis of the LID Algorithm  
At the center of the algorithm above is the notion of the locally heaviest edge [8; 9], since the nodes send PROP and REJ messages in order to compare their heaviest edges and find the locally heaviest ones. Note here that we assume unique edge weights, since it is important for the greedy algorithms described here to be able to recognize the locally heaviest edges in an unambiguous way (ties can be broken using node identities). However, globally unique edge weights are not necessary: it is sufficient for edge weights to be unique in the local neighborhoods of their endpoint nodes. By the definition in Section 2, at most, one locally heaviest edge can be attached to a node \(i\) at any specific point during the execution of the algorithm. However, once an edge is selected by node \(i\), another one can possibly become locally heaviest in node \(i\)'s neighborhood, and so on, until the algorithm selects enough of them. On the other hand, when nearby nodes fill in their quotas of possible connections, any  
**Proof:** Based on Lemma 3, by the end of the algorithm, all chosen edges of node \(i\) have been locally heaviest. Furthermore, if there is enough quota \(b_{i}\) available, any unselected locally heaviest edges will be eventually selected. The only way some locally heaviest edge has been left unchosen is for node \(i\) to fill in its connection quota \(b_{i}\) with other locally heaviest edges. We just need to prove that in this case the unchosen edge is of lower weight than the chosen ones. Note that the LID algorithm proposes to nodes of heavier edges first and proceeds only if it receives an explicit decline (meaning it was not a locally heaviest edge or the other node filled its quota), so the chosen edges are always heavier than any unchosen one. \(\Box\)  
Calculating edge weights in the way previously described enables the conversion of the original maximizing satisfaction b-matching problem of Section 2 to a many-to-many maximum weighted matching problem, but as an added benefit it enables us to use the weight lists to make preference-based decisions, in a way similar to a b-matching problem. This new b-matching problem does not replace the original maximizing satisfaction b-matching: the nodes keep their original preference lists, but a new b-matching problem arises when they try to cooperate in order to collectively achieve a guaranteed level of connection quality. However, this new b-matching problem always converges regardless of the original problem, due to the symmetric nature of the edge weights [4]. The following lemma expresses exactly this property by showing that the algorithm terminates for all nodes. **Lemma 5**: _Algorithm LID terminates for every node \(i\in V\)._  
**Proof:** From the code of Algorithm LID we can see that it terminates for node \(i\) when \(U_{i}=\emptyset\) or \(P_{i}\backslash K_{i}=\emptyset\), that is, when every neighbor replies (and node \(i\) gets less than \(b_{i}\) positive replies) or enough neighbors reply (for node \(i\) to get \(b_{i}\) positive replies), respectively. The only case where the algorithm would not terminate is if some node would wait indefinitely for a neighbor's answer, _i.e._, 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}\). In order to prove that the algorithm terminates, we only need to prove that communication cycles cannot exist. Assume there is a communication cycle \(\{n_{0},n_{1},\ldots,n_{k-1}\}\). Since node \(n_{i\bmod k}\) sent a PROP message to node \(n_{(i+1)\mod k}\) and not to node \(n_{(i-1)\mod k}\), we know that \(w(n_{i\mod k},n_{(i+1)\mod k})>w(n_{i\mod k},n_{(i-1)\mod k})\).