A Self-Stabilizing Algorithm for Maximal Matching in Link-Register Model
| Autor: | George Manoussakis, Devan Sohier, Laurence Pilard, Johanne Cohen |
|---|---|
| Přispěvatelé: | Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Parallélisme Réseaux Algorithmes Distribués (LI-PaRAD), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Zvi Lotker, Boaz Patt-Shamir |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Atomicity
[SCCO.COMP]Cognitive science/Computer science 0102 computer and information sciences 02 engineering and technology Link register Link-Register Model 01 natural sciences Self-Stabilizing 010201 computation theory & mathematics Distributed algorithm Distributed Algorithm 020204 information systems 0202 electrical engineering electronic engineering information engineering Daemon Maximal Matching Algorithm Mathematics |
| Zdroj: | SIROCCO 2018: International Colloquium on Structural Information and Communication Complexity SIROCCO 2018: International Colloquium on Structural Information and Communication Complexity, Jun 2018, Ma'ale HaHamisha, Israel. pp.14-19 Structural Information and Communication Complexity ISBN: 9783030013240 SIROCCO |
| Popis: | This paper presents a new distributed self-stabilizing algorithm solving the maximal matching problem under the fair distributed daemon. This is the first maximal matching algorithm in the link-register model under read/write atomicity. This work is composed of two parts. As we cannot establish a move complexity analysis under the fair distributed daemon, we first design an algorithm \(\mathcal A_{1} \) under the unfair distributed daemon dealing with some relaxed constraints on the communication model. Second, we adapt \(\mathcal A_{1} \) so that it can handle the fair distributed daemon, leading to the \(\mathcal A_{2} \) algorithm. We prove that algorithm \(\mathcal A_1\) stabilizes in \(O(m\Delta )\) moves and algorithm \(\mathcal A_2\) in \(O(m\Delta )\) rounds, with \(\Delta \) the maximum degree and m the number of edges. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|