## 1 Introduction  
Overlays represent a significant puzzle piece in contemporary and future networking infrastructure, whether they are intended to support resource sharing or other collaborative applications, such as searching, _ad hoc_ connectivity and persistent services. The common scenario is that peers are able to know part of the overlay network (in terms of potential neighbors), but want to connect only to a small number of other peers in order to conserve resources. Connection decisions are not to be taken blindly, but should rather be based on some suitability metric related to, e.g., the peer's distance, interests, recommendations, transaction history or available resources. In the fully distributed scenario, every peer may follow an individually chosen metric (that it may even not want to disclose to other peers), but still wants to be able to coordinate with others in order to improve the quality of its connections. We present algorithms that enable peers that follow them to achieve a guaranteed level of collective quality in their connections. They achieve that by disclosing a limited amount of metric information to their immediate neighbors, but not the metric itself and are, in fact, independent of any individual metric choices. At the same time, the algorithms proposed here are able to adapt and tolerate the high dynamicity commonly found in these resource sharing overlays, with peers leaving, joining or changing the metrics about their neighbors at any time. Observe that finding good methods to help peers establish connections and accommodate such needs or preferences relates to some form of _matching problem_ in a graph. Moreover, in the context of overlay networks, an important goal is to enable peers to satisfy their preferences during overlay construction: note that these \"preference lists\" point towards a form of stable marriage/roommates problem [1; 2; 3]. The first to observe the relation between overlay construction and stable marriage problems were [PERSON] _et al._[4], followed by [PERSON] [5], in which overlay construction is regarded as a _generalized_ stable roommates matching problem [6] (also referred to as a _b-matching_ problem [5; 7]). In such a problem, the agents under consideration have more than one opportunity to connect to each other, in a similar way to, e.g., attendees in a conference exchanging the limited amount of calling cards they brought with them. The goal for each agent in this setting is to be able to form the desired amount of connections with the highest quality (most preferred) neighbors. However, the existence of cycles among the preference lists of the peers may turn overlay construction into a challenging task: matchings between peers on a cycle always create opportunities for improvement at other sites in the network, leading to infinite loops and unstable configurations. [PERSON] _et al._ in [4] proved that, in the case of an acyclic preference system, there is always a stable configuration and also supplied examples of preference systems based on global or symmetric metrics. Furthermore, in order to give a qualitative measure of the stabilization process, [PERSON] in [5] defined the notion of _satisfaction_ gleaned by a peer out of its current matching choices. With the research focused on preference systems that are known to have a stable configuration, such as acyclic ones, there is a relative scarcity of results concerning _arbitrary_ preference systems and practical algorithms for achieving stable configurations (if existing) or good approximations thereof. Can we look at this problem from a different perspective? How can a solution be measured? What are the characteristics of a practical algorithm in a fully distributed scenario? Can we adapt to and tolerate changes in the overlay, such as preference change or peer joining/leaving?