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).

• Zhengnan Shi

• self-stabilization
• popular matching
• algorithm
• distributed computing
• fault tolerance

[1] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular
matchings. SIAM J. Comput., 37(4):1030-1045, 2007.
[2] 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.
[3] E. W. Dijkstra. Self-stabilizing systems in spite of distributed control.
Comm. ACM, 17(11):643-644, Jan. 1974.
[4] S. Dolev. Self-Stabilization. MIT Press, 2000.
[5] S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing
leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4),
1995.
[6] D. Gale and L. S. Shapley. College admissions and the stability of
marriage. American Mathematical Monthly, 69:9-15, 1962.
[7] P. Gardenfors. Match making: assignments based on bilateral preferences.
Behavioral Sciences, 20:166-173, 1975.
[8] D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure
and Algorithms. MIT Press, 1989.
[9] P. Hall. On representatives of subsets. Journal of the London
Mathematical Society, 10:26-30, 1935.
[10] 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.
[11] S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal
matching. Inform. Process. Lett., 43:77-81, 1992.
[12] A. Panconesi and A. Srinivasan. The local nature of -coloring and its
algorithmic applications. Combinatorica, 15:225-280, 1995.
[13] S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation
algorithms for set cover and covering integer programs. SIAM J.
Comput., 28:525-540, 1998.
[14] 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.
[15] G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge
University Press, Cambridge UK, 2000.