PODC 2010 · 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Zurich, Switzerland, July 2010 · doi:10.1145/1835698.1835765

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

ISBN 978-1-60558-888-9

- Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela: Almost stable matchings by truncating the Gale–Shapley algorithm ·
*Algorithmica*58:102–118, 2010