On the complexity of distributed stable matching with small messages |
| |
Authors: | Alex Kipnis Boaz Patt-Shamir |
| |
Affiliation: | (2) Department of Computing Science, University of Glasgow, Glasgow, UK |
| |
Abstract: | We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). 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 unmatched 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 matching problem requires ${Omega(sqrt{n/Blog n})}We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). 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 unmatched 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 matching problem requires W(?{n/Blogn}){Omega(sqrt{n/Blog n})} communication rounds in the worst case, even for graphs of diameter O(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(?n){O(sqrt n)} blocking pairs, and if a pair is considered blocking only if they like each other much more then their assigned match. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|