Patrik Floréen · Petteri Kaski · Valentin Polishchuk · Jukka Suomela

Brief announcement: Distributed almost stable marriage

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

authors’ version publisher’s version

Abstract

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.

Publication

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

Links

Journal Version

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.