Stable Matching as a Means of Allocating Distributed Resources

This is preliminary work, done as part of a group project by the distributed systems group lead by Professor Abdelsalam Heddaya.

Abstract

The stable matching family of algorithms promises to help achieve local optima in a distributed system for the exchange of computational resources. The problem is to match requests to resources in a system where lack of central control precludes global optimization.

The stable marriage problem was first described in [Gale-Shapley62]. Some variations and extensions of the original algorithm that are applicable to distributed resource allocation are considered. Furthermore, the complexity of the problem as it relates to the expected efficiency of a practical system, is reviewed and shown not to impede the practicality of the approach.