## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### Analysis of the AdaptiveLID Algorithm  
The following lemmas prove that the algorithm always converges after a finite amount of steps or, in the case of changes in the network, in a finite amount of steps after the changes stop. Although implied by the distributed nature of the algorithm, it is useful to note that the algorithm continues to run at all nodes regardless of any changes that are happening in the network. In fact, as we show in the experimental section, it manages to maintain a reduced but steady level of service while under extremely heavy stress or possibly a network attack. However, convergence can be guaranteed after all changes complete, since any changes that might occur require appropriate readjustment by the distributed algorithm. **Lemma 6**: _In a failure-free execution, edge weight updates that are caused by node or preference changes complete in a finite amount of time._  
Proof. : When a node joins (leaves) the network, it gets inserted to (deleted from) neighboring nodes' preference lists, causing changes that need to be communicated to their own neighbors. The same happens to the node itself when it changes its own preference list. Therefore, every change causes a weight update that propagates at a maximum distance of two and to a bounded amount of nodes (bounded by the size of a distance of two neighborhood from the originating node). Note that the neighbor's neighbors (or the immediate neighbors in the case of simple preference change) accept the weight update passively and do not propagate it further. Since we assumed that nodes do not fail and messages do not get lost, it is evident that all nodes are fully updated in a finite amount of time after the change. We define as _available_, with respect to node \(i\), a node \(j\) in the neighborhood of node \(i\) that has neither been proposed by node \(i\) nor rejected node \(i\). A node \(j\) is the _locally heaviest node_ in the neighborhood of node \(i\) at some point in time if there are no available nodes adjacent to node \(i\) that are endpoints of heavier edges. Note that edges with such a node as an endpoint are candidates for being locally heaviest edges (hence, the name \"locally heaviest node\"). In fact, when the endpoints of an edge consider simultaneously each other locally heaviest, the edge between them is the locally heaviest edge. **Lemma 7**: _In a finite amount of time after a node or preference change, every node cancels all proposals towards neighbors that are no longer locally heaviest and issues an equal amount towards available neighbors that are locally heaviest._  
Proof. : Every change triggers weight updates at a distance of one (nodes that the joining/leaving node connect to/disconnect from or direct neighbors of a node that changes preferences) and possibly at a distance of two (neighbor's neighbors of a joining/leaving node). By Lemma 6, the weight updates complete in a finite amount of time. When procedure 3 executes next in any node \(i\) at a distance of one or two from the change, it will repeatedly examine nodes that are either available or have simultaneously rejected and been rejected by node \(i\), as long as they are heavier than the proposed node of the lowest weight. Every time it encounters a node of the latter category, it sends a WAKE message, prompting the node to revoke its rejection, whereas every time it encounters a node of the former category, it sends a PROP message, preceded by a REJ to the proposed node of the lowest weight (note that whether anode is considered locally heaviest or not may change during a single execution of procedure 3.). In any case, at the end of procedure 3's execution, all proposals from node \(i\) to its neighbors that are no longer locally heaviest are canceled, and complementary proposals are sent to available neighbors that are locally heaviest; the same is true for every node in the network.