Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Research highlights
Research results
Research highlight : SELF-STABILIZING DISTRIBUTED STABLE MARRIAGE
SELF-STABILIZING DISTRIBUTED STABLE MARRIAGE
5 November 2017

Stable matching (also called stable marriage in the literature)
is a problem of matching in a bipartite graph, introduced in an economic context by Gale and Shapley. In this problem, each node has preferences for matching with its neighbors. The final matching should satisfy these preferences such that in no unmatched pair both nodes prefer to be matched together. The problem has a lot of useful applications (two sided markets, migration of virtual machines in Cloud computing, content delivery on the Internet, etc.). There even exists companies dedicated solely to administering stable matching programs. Numerous algorithms have been designed for solving this problem (and its variants), in different contexts, including distributed ones. However, to the best of our knowledge, none of the distributed solutions is self-stabilizing (self-stabilization is a formal framework that allows dealing with transient corruptions of memory and channels). We present a self-stabilizing stable matching solution, in the model of composite atomicity (state-reading model), under an unfair distributed scheduler. The algorithm is given with a formal proof of correctness and an upper bound on its time complexity in terms of moves and steps.



Keyword
  ° Distributed algorithms

Group
  ° Graphs, ALgorithms and Combinatorics
  ° Parallel Systems

Contact
  ° BURMAN Janna
Research highlights
BEST STUDENT PAPER AWARD (ML) AT ECML 2019
20 September 2019
Guillaume Doquet (A&O) received the Best Student Paper Award (category Machine Learning) at ECML 201

BEST PAPER AWARD - HPCS 2019 - ON SERVER-SIDE FILE ACCESS PATTERN MATCHING
17 July 2019
Francieli Zanon Boito¹ , Ramon Nou², Laércio Lima Pilla³, Jean Luca Bez⁴, Jean-François Méhaut¹, T

BEST FULL PAPER AWARD EDM 2019 - EDUCATIONAL DATA MINING
5 July 2019
DAS3H: Modeling Student Learning and Forgetting for Optimally Scheduling Distributed Practice of Ski

BEST PAPER AWARD - CODIT2019 - STOCHASTIC DUAL DYNAMIC INTEGER PROGRAMMING FOR A MULTI-ECHELON LOT-SIZING PROBLEM WITH REMANUFACTURING AND LOST SALES
14 May 2019
Franco Quezada, Céline Gicquel and Safia Kedad-Sidhoum

BEST PAPER AWARD ICONS 2019: RESONANCE THINKING AND INDUCTIVE MACHINE LEARNING
6 May 2019
Yves Kodratoff & Marta Franova