Maximum Matching for Anonymous Trees with Constant Space per Process

Datta, Ajoy K.; Larmore, Lawrence L.; Masuzawa, Toshimitsu

doi:10.4230/LIPIcs.OPODIS.2015.16

File

LIPIcs.OPODIS.2015.16.pdf

Filesize: 0.54 MB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.OPODIS.2015.16
URN: urn:nbn:de:0030-drops-66074

Author Details

Ajoy K. Datta

Lawrence L. Larmore

Toshimitsu Masuzawa

Cite AsGet 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.

Keywords

anonymous tree
maximum matching
self-stabilization
unfair daemon

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.