Name
Abstract | ||
|---|---|---|
"Stable marriage" refers to a particular matching with constraints having a wide variety of applications in different domains (two-sided markets, Cloud computing, college admissions, etc.). Most of the studies on this problem performed up to now were for centralized and synchronous settings assuming initialization. We consider a distributed and asynchronous context, without initialization (i.e., in a self-stabilizing manner, tolerating any transient fault) and with some confidentiality requirements. The single already known self-stabilizing solution in Laveau et al. (SSS' 2017), based on Ackerman et algorithm (SICOMP' 2011), stabilizes in O(n(4)) moves (activation of a single node). We improve on this previous result considerably by presenting a solution with O(n(2)) steps, relying on the idea of Gale and Shapley's algorithm (AMM 1962), which takes also O(n(2)) moves, but in a centralized synchronous context. Moreover it is not self-sabilizing solution and a corruption cannot be repaired locally, as noticed by Knuth (1976). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-030-03232-6_26 | STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2018 |
DocType | Volume | ISSN |
Conference | 11201 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joffroy Beauquier | 1 | 448 | 53.52 |
| Thibault Bernard | 2 | 0 | 0.34 |
| Janna Burman | 3 | 123 | 13.55 |
| Shay Kutten | 4 | 2118 | 226.75 |
| Marie Laveau | 5 | 0 | 0.34 |