We study the stable marriage problem in a distributed setting. The communication network is a bipartite graph, with men on one side and women on the other. Acceptable partners are connected by edges, and each participant has chosen a linear order on the adjacent nodes, indicating the matching preferences. The classical Gale–Shapley algorithm could be simulated in such a network to find a stable matching. However, the stable matching problem is inherently global: the worst-case running time of any distributed algorithm is linear in the diameter of the network. Our work shows that if we tolerate a tiny fraction of unstable edges, then a solution can be found by a fast local algorithm: simply truncating a distributed simulation of the Gale–Shapley algorithm is sufficient. Among others, this shows that an almost stable matching can be maintained efficiently in a very large network that undergoes frequent changes.
Andrea Richa and Rachid Guerraoui (Eds.): PODC’10, Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing, July 25–28, 2010, Zurich, Switzerland, pages 281–282, ACM Press, New York, 2010