A Self-stabilizing Algorithm for Maximum Popular Matching of Strictly Ordered Preference Lists
In this paper, we consider the problem of Popular Matching of strictly ordered preference lists. A Popular Matching is not guaranteed to exist in any network. We propose an IDbased, constant space, self-stabilizing algorithm that converges to a Maximum Popular Matching an optimum solution, if one exist. We show that the algorithm stabilizes in O(n5) moves under any scheduler (daemon).
 D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular
matchings. SIAM J. Comput., 37(4):1030-1045, 2007.
 J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. Selfstabilizing
local mutual exclusion and daemon refinement. In International
Symposium on Distributed Computing, pages 223-237, 2000.
 E. W. Dijkstra. Self-stabilizing systems in spite of distributed control.
Comm. ACM, 17(11):643-644, Jan. 1974.
 S. Dolev. Self-Stabilization. MIT Press, 2000.
 S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing
leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4),
 D. Gale and L. S. Shapley. College admissions and the stability of
marriage. American Mathematical Monthly, 69:9-15, 1962.
 P. Gardenfors. Match making: assignments based on bilateral preferences.
Behavioral Sciences, 20:166-173, 1975.
 D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure
and Algorithms. MIT Press, 1989.
 P. Hall. On representatives of subsets. Journal of the London
Mathematical Society, 10:26-30, 1935.
 S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani.
Self-stabilizing algorithms for minimal dominating sets and maximal
independent sets. Comput. Math. Appl., 46(5-6):805-811, 2003.
 S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal
matching. Inform. Process. Lett., 43:77-81, 1992.
 A. Panconesi and A. Srinivasan. The local nature of -coloring and its
algorithmic applications. Combinatorica, 15:225-280, 1995.
 S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation
algorithms for set cover and covering integer programs. SIAM J.
Comput., 28:525-540, 1998.
 Z. Shi, W. Goddard, and S. T. Hedetniemi. an anonymous selfstabilizing
algorithm for 1-maximal independent set in trees. Information
Processing Letters, 91(2):77-83, 2004.
 G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge
University Press, Cambridge UK, 2000.