
Open access
Author
Khanchandani, Pankaj
Wattenhofer, Roger
Date
2017Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Consider a complete bipartite graph of 2n nodes with n nodes on each side. In a round, each node can either send at most one message to a neighbor or receive at most one message from a neighbor. Each node has a preference list that ranks all its neighbors in a strict order from 1 to n. We introduce a non-negative similarity parameter D < n for the preference lists of nodes on one side only. For D = 0, these preference lists are same and for D = n-1, they can be completely arbitrary. There is no restriction on the preference lists of the other side. We show that each node can compute its partner in a stable matching by receiving O(n(D + 1)) messages of size O(log n) each. We also show that this is optimal (up to a logarithmic factor) if D is constant. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000192042Publication status
publishedBook title
20th International Conference on Principles of Distributed Systems (OPODIS 2016)Journal / series
Leibniz International Proceedings in InformaticsVolume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
distributed stable matching; similar preference lists; stable matching; stable marriageMore
Show all metadata
ETH Bibliography
yes
Altmetrics