## 1 Introduction
To propose answers to these questions, we focus on the distributed b-matching problem: we suggest a novel modeling, present algorithms for both its adaptive and non-adaptive forms, show convergence and guaranteed approximation bounds and complement our results with an extensive experimental study. * **Novel modeling:**We start by reflecting further on the evaluation of different matching choices of peers (as proposed in [5]). By considering satisfaction about the peer's connection choices(compared to the optimal choices) as an optimization metric, we focus on distributed algorithms that try to maximize the satisfaction of peers that follow them (either a group or the whole overlay). We then proceed to propose a method of constructing an acyclic preference system from any arbitrary one, and we use this helper acyclic system to reduce the initial problem to a many-to-many maximum weighted matching problem. * **Algorithmic solutions:**Generalizing the approximation algorithm for the one-to-one matching problem found in [8, 9], we present a simple, fully distributed, \(\frac{1}{2}\)-approximation algorithm for the many-to-many maximum weighted matching problem using only communication among immediate neighbors. In addition, we complement our distributed algorithm with a variant that can adapt to and tolerate changes in the overlay, such as peer joining/leaving and preference changes. We prove that both algorithms converge and that their computed solution is at least \(\frac{1}{2}\left(1+b_{\max}^{-1}\left(1+\frac{1-b_{\max}^{-1}}{2s+b_{\max}^{ -1}}\right)\right)\) of the maximum total satisfaction of the initial system, where \(b_{\max}\) is the maximum connection quota in the graph and \(s=\frac{L_{\max}}{L_{\min}}\) is the ratio of the maximum and minimum neighbor list sizes in the graph, \(L_{\max}\) and \(L_{\min}\), respectively, resulting in a \(\frac{1}{4}\left(1+b_{\max}^{-1}\left(1+\frac{1-b_{\max}^{-1}}{2s+b_{\max}^{ -1}}\right)\right)\)-approximation algorithm in total. * **Experimental study:** We also provide an extensive experimental study of the behavior of the algorithm under a variety of scenarios, including normal operation, but also operation under high stress. Under normal operation, we focus on the levels of achieved satisfaction, as well as convergence time (in the case of our non-adaptive algorithm) and reconvergence time (in the case of our adaptive algorithm). Specifically, we show that the resulting satisfaction is always significantly higher than the worst-case theoretical bound after convergence, but also remains at high levels during and after reconvergence, while reconvergence is achieved in an efficient way under a variety of changes. Besides, motivated by [10, 11], we conducted experiments that focus on the stability of the network under join/leave attacks, by exposing it to high churn rates, and observed that the algorithm withstands the attacks while maintaining graceful satisfaction values throughout them. The rest of the paper is organized as follows. In Section 2, we introduce the necessary notation and define our problem, while in Section 3, we present, separately, the notion of node satisfaction, along with an extensive commentary, due to its importance in our modeling. In Section 4, we show how our original b-matching problem can be reduced into a many-to-many maximum weighted matching problem that is guaranteed to have a stable solution, and we prove that this can be done with constant factor approximation. We present our distributed algorithm for the many-to-many maximum weighted matching problem in two variations, adaptive and non-adaptive, in Section 5, along with analytical proofs of their approximation ratio for our original problem. Our extensive experimental study can be found in Section 6, while discussion on the presented, as well as related work can be found in Section 7. Finally, Section 8 concludes the paper.