Portal de Periódicos da CAPES

Self-stabilizing Distributed Stable Marriage

2017; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-69084-1_4

1611-3349

Marie Laveau, George Manoussakis, Joffroy Beauquier, Thibault Bernard, Janna Burman, Johanne Cohen, Laurence Pilard,

Logic, Reasoning, and Knowledge

Stable marriage 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 exist 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.