## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### AdaptiveLID Algorithm  
In a dynamic setting, where nodes join/leave the network or change preferences about their neighbors at any time, there is a partial or full solution that is disturbed by a specific operation. In this case, it is desirable to \"repair\" the solution locally instead of recomputing it globally. It would also be advantageous to limit the repairs to the neighborhood of the operation, so that far enough nodes would remain unaffected. Note that the locally-heaviest-edge property that we are using here seems ideal for this purpose: it only makes sense to preserve and use it further to support dynamicity.  
In the adaptive algorithm, AdaptiveLID presented here, all three cases of dynamicity mentioned above (join/leave/change) are supported. In the case of a joining (respectively departing) node, neighboring nodes add (respectively delete) it to (respectively from) their preference lists. On the other hand, when a node changes preferences, no change occurs to the neighboring nodes' preference lists, but edge weights may change radically. A common thread between these cases is that the nodes directly involved in the operations must recalculate their marginal satisfactions for their neighbors and exchange them so that their adjacent edges have the correct weights. Afterwards, they must re-evaluate their connections: if they are not locally heaviest any more, the nodes abandon the least weighted ones and try to get matched with the locally heaviest ones. Note here that this method avoids the recalculation of the solution over the whole network, instead limiting it to a neighborhood around the network area where the dynamic operation took place. An additional benefit is that the involved nodes maintain their current connections unless proven to be non-optimal, _i.e._, they change them only if necessary.  
The AdaptiveLID algorithm uses at each node \(i\) five sets (\(P_{i},K_{i},A_{i},R_{i},B_{i}\)) and an incoming message queue, \(queue_{i}\), and sends three kinds of messages (PROP, REJ and WAKE):  
* A node \(i\) sends PROP messages to propose to its heaviest-weight neighbors the establishment of a connection. If an asked node also sends a PROP message to node \(i\), then the connection is established (_locked_): note that this will happen at both endpoints. Set \(P_{i}\) stores the neighbors to which node \(i\) proposed with a PROP message; \(A_{i}\) stores the neighbors that approached node \(i\) with a PROP message; \(K_{i}\) stores the locked neighbors; \(B_{i}\) stores the neighbors that rejected node \(i\), and \(R_{i}\) the neighbors that node \(i\) rejected. Sets \(B_{i}^{*}\) and \(A_{i}^{*}\) are copies of sets \(B_{i}\) and \(A_{i}\), respectively, that do not contain neighbors of edges heavier than the edge of the worst connected neighbor.
* A node sends a REJ message when it has locked as many neighbors as it could. Nodes can send additional PROP messages to available neighbors if they receive a REJ message. PROP messages are sent to neighbors in decreasing ranking order, and there are at most \(b_{i}\) such unanswered messages originating from \(i\) at any time.
* Node \(i\) is constantly checking if its PROP messages are addressed to heaviest-weight neighbors, as ranking can change due to a change in the network. If it detects a better available node than the currently proposed ones, it sends a REJ message to the worst connected neighbor and a PROP to the better candidate. However, if the better candidate has simultaneously rejected and been rejected by node \(i\), node \(i\) sends only a WAKE message.