A Note on Distributed Stable Matching

We consider the distributed complexity of the stable marriage problem. In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable marriage problem requires Omega (radicn/B log n) communication rounds in the worst case, even for graphs of diameter Theta (log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(radicn) blocking pairs. We also consider epsiv-stability, where a pair is called epsiv-blocking if they can improve the quality of their match by more than an epsilon fraction, for some 0 les e les 1. Our lower bound extends to epsiv-stability where epsiv is arbitrarily close to 1/2. We also present a simple distributed algorithm for epsiv-stability whose time complexity is O(n/epsiv).