Overlays with preferences: Approximation algorithms for matching with preference lists

摘要

A key property of overlay networks, that is going to play an important part in future networking solutions, is the peers'' ability to establish connections with other peers based on some suitability metric related to e.g. the node''s distance, interests, recommendations, transaction history or available resources. Each node may choose individually an appropriate metric and try to connect or be matched with the available peers that it considers best. When there are no preference cycles among the peers, it has been proven that a stable matching exists, where peers have maximized the individual satisfaction gleaned of their choices. However, no such guarantees are currently being given for the cases where cycles may exist and known methods may not be able to resolve “oscillations” in preference-based connectivity and reach stability. In this work we employ the use of node satisfaction to move beyond classic stable matchings and towards the overlay network context. We present a simple yet powerful distributed algorithm that uses aggregate satisfaction as an optimization metric. The algorithm is a generalization of an approximation one-to-one matching algorithm, into the many-to-many case. We prove that the total satisfaction achieved by our algorithm is a constant factor approximation of the maximum total satisfaction in the network, depending also on the maximum number of possible connections of a peer in the overlay.