2026-08-10T10:24:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6607 2024-03-06T10:36:50Z ddc:004 open_access

Maximum Matching for Anonymous Trees with Constant Space per Process Datta, Ajoy K. Larmore, Lawrence L. Masuzawa, Toshimitsu anonymous tree maximum matching self-stabilization unfair daemon 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ajoy K. Datta and Lawrence L. Larmore and Toshimitsu Masuzawa 2016 Is Part Of LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2015.16 urn:nbn:de:0030-drops-66074 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.16 eng https://creativecommons.org/licenses/by/3.0/legalcode