LIPIcs.OPODIS.2015.16.pdf
- Filesize: 0.54 MB
- 16 pages
Document
Maximum Matching for Anonymous Trees with Constant Space per Process
Authors
-
Part of:
Volume:
19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-10-13
Cite As Get BibTex
Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Maximum Matching for Anonymous Trees with Constant Space per Process. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.OPODIS.2015.16
Abstract
We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.
Subject Classification
Keywords
- anonymous tree
- maximum matching
- self-stabilization
- unfair daemon
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Y. Asada and M. Inoue. A silent self-stabilizing algorithm for 1-maximal matching in anonymous networks. In Proc. WALCOM 2015, pages 187-198, 2015.
-
J.R.S. Blair and F. Manne. Efficient self-stabilizing algorithms for tree networks. In Proc. ICDCS 2003, pages 20-26, 2003.
-
S. Chattopadhyay, L. Higham, and K. Seyffarth. Dynamic and self-stabilizing. In Proc. PODC 2002, pages 290-297, 2002.
-
A. K. Datta and L. L. Larmore. Leader election and centers and medians in tree networks. In Proc. SSS 2013, pages 113-132, 2013.
-
E.W. Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the ACM, 17:643-644, 1974.
-
W. Goddard, S.T. Hedetniemi, D.P. Jacobs, and P.K. Srimani. Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. In Proc. IPDPS 2003, page 162, 2003.
-
W. Goddard, S.T. Hedetniemi, and Z. Shi. An anonymous self-stabilizing algorithm for 1-maximal matching in trees. In Proc. PDPTA 2006, pages 797-803, 2006.
-
N. Guellati and H. Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. Journal of Parallel and Distributed Computing, 70(4):406-415, 2010.
-
S.T. Hedetniemi, D.P. Jacobs, and P.K. Srimani. Maximal matching stabilizes in time O(m). Information Processing Letters, 80(5):221-223, 2001.
-
S.C. Hsu and S.T. Huang. A self-stabilizing algorithm for maximal matching. Information Processing Letters, 43(2):77-81, 1992.
-
M.H. Karaata and K.A. Saleh. A distributed self-stabilizing algorithm for finding maximum matching. Computer Systems Science and Engineering, 15(3):175-180, 2000.
-
M. Kimoto, T. Tsuchiya, and T. Kikuno. The time complexity of Hsu and Huang’s self-stabilizing maximal matching algorithm. IEICE Trans. Infrmation and Systems, E93-D(10):2850-2853, 2010.
-
F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A new self-stabilizing maximal matching algorithm. In Proc. SIROCCO 2007, pages 96-108, 2007.
-
F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A self-stabilizing 2/3-approximation algorithm for the maximum matching problem. Theoretical Computer Science, 412(4):5515-5526, 2011.
-
G. Tel. Maximal matching stabilizes in quadratic time. Information Processing Letters, 49(6):271-272, 1994.