DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.12

Distributed Stable Matching with Similar Preference Lists

Authors: Pankaj Khanchandani and Roger Wattenhofer

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

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.

Cite as

Pankaj Khanchandani and Roger Wattenhofer. Distributed Stable Matching with Similar Preference Lists. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{khanchandani_et_al:LIPIcs.OPODIS.2016.12,
  author =	{Khanchandani, Pankaj and Wattenhofer, Roger},
  title =	{{Distributed Stable Matching with Similar Preference Lists}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.12},
  URN =		{urn:nbn:de:0030-drops-70811},
  doi =		{10.4230/LIPIcs.OPODIS.2016.12},
  annote =	{Keywords: distributed stable matching, similar preference lists, stable matching, stable marriage}
}

Search Results

Documents authored by Khanchandani, Pankaj

Distributed Stable Matching with Similar Preference Lists

Abstract

Cite as

Thanks for your feedback!

Could not send message