A new self-stabilizing maximal matching algorithm

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n^2) and O(@dm) to O(m) where n is the number of processes, m is the number of edges, and @d is the maximum degree in the graph.

• Publication year

  2007

• Venue

  Theoretical Computer Science

• Publication date

  2007-01-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2008.12.022arXiv cs/0701189
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Stabilization, Safety, and Security of Distributed Systems

  2011cited by this paper
• A Self-stabilizing Weighted Matching Algorithm

  2007cited by this paper
• A Self-Stabilizing Algorithm for Maximum Matching in Trees

  2007cited by this paper
• Conflict Managers for Self-stabilization without Fairness Assumption

  2007cited by this paper
• An Anonymous Self-Stabilizing Algorithm for 1-Maximal Matching in Trees

  2006cited by this paper
• Self Stabilization

  2004cited by this paper
• Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks

  2003cited by this paper
• Efficient self-stabilizing algorithms for tree networks

  2003cited by this paper
• Dynamic and self-stabilizing distributed matching

  2002influential reference
• Self-stabilizing Neighborhood Unique Naming under Unfair Scheduler

  2001cited by this paper
• Maximal matching stabilizes in time O(m)

  2001cited by this paper
• SuperStabilizing protocols for dynamic distributed systems

  1995cited by this paper
• Maximal Matching Stabilizes in Quadratic Time

  1994cited by this paper
• A Self-Stabilizing Algorithm for Maximal Matching

  1992influential reference
• Local and global properties in networks of processors (Extended Abstract)

  1980cited by this paper
• Self-stabilizing systems in spite of distributed control

  1974cited by this paper

• Byzantine Stable Matching

  2025cites this paper
• The R(1)W(1) Communication Model for Self-Stabilizing Distributed Algorithms

  2025cites this paper
• Towards Learning-Augmented Peer-to-Peer Networks: Self-Stabilizing Graph Linearization with Untrusted Advice

  2025influential citation
• Self-Stabilizing Fully Adaptive Maximal Matching

  2024cites this paper
• Analyzing Program Transitions to Compute Benefit of Tolerating Consistency Violation Faults

  2023cites this paper
• Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach

  2022cites this paper
• Technical Report: Using Static Analysis to Compute Benefit of Tolerating Consistency

  2021cites this paper
• Analyzing the Effect of Consistency Violation Faults in Self-Stabilizing Programs

  2021cites this paper
• Technical Report: Benefits of Stabilization versus Rollback in Self-Stabilizing Graph-Based Applications on Eventually Consistent Key-Value Stores

  2020cites this paper
• Benefits of Stabilization versus Rollback in Self-Stabilizing Graph-Based Applications on Eventually Consistent Key-Value Stores

  2020cites this paper
• Self-Stabilizing Domination Algorithms

  2020cites this paper
• A self-stabilizing algorithm for b-matching

  2019cites this paper
• Polynomial Silent Self-Stabilizing p-Star Decomposition†

  2019cites this paper
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

  2019influential citation
• Parallelism

  2019cites this paper
• Parameterized synthesis of self-stabilizing protocols in symmetric networks

  2019cites this paper
• Benefits of Stabilization versus Rollback in Eventually Consistent Key-Value Stores

  2019cites this paper
• Self-stabilization and Byzantine Tolerance for Maximal Matching

  2018cites this paper
• Parameterized Synthesis of Self-Stabilizing Protocols in Symmetric Rings

  2018cites this paper
• A Self-Stabilizing Algorithm for Maximal Matching in Link-Register Model

  2018cites this paper
• Evaluating Fault Tolerance Properties of Self-Stabilizing Matching Algorithms in Wireless Sensor Networks

  2018influential citation
• Structural Information and Communication Complexity

  2018cites this paper
• Benefit of self-stabilizing protocols in eventually consistent key-value stores: a case study

  2018cites this paper
• Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks

  2017cites this paper
• A O(m) Self-Stabilizing Algorithm for Maximal Triangle Partition of General Graphs

  2017cites this paper
• A self-stabilizing algorithm for maximal matching in link-register model in $O(nΔ^3)$ moves

  2017cites this paper
• Polynomial Silent Self-Stabilizing Maximal p-Star Decomposition

  2017cites this paper
• Self-stabilizing algorithms in wireless sensor networks

  2017cites this paper
• ASSESS: A Tool for Automated Synthesis of Distributed Self-stabilizing Algorithms

  2017cites this paper
• An Efficient Silent Self-stabilizing 1-Maximal Matching Algorithm Under Distributed Daemon for Arbitrary Networks

  2017cites this paper
• An Efficient Silent Self-stabilizing 1-Maximal Matching Algorithm Under Distributed Daemon Without Global Identifiers

  2016cites this paper
• Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

  2016cites this paper
• Self-Stabilizing Maximal Matching and Anonymous Networks

  2016cites this paper
• Polynomial self-stabilizing algorithm and proof for a 2/3-approximation of a maximum matching

  2016cites this paper
• Self-Stabilization - A Mechanism to Make Networked Embedded Systems More Reliable?

  2016cites this paper
• Stabilization, Safety, and Security of Distributed Systems

  2016cites this paper
• A Self-Stabilizing Algorithm for Maximal Matching in Anonymous Networks

  2016influential citation
• Self-stabilizing algorithms for graph parameters

  2015cites this paper
• Maximum Matching for Anonymous Trees with Constant Space per Process

  2015cites this paper
• Automated Synthesis of Timed and Distributed Fault-Tolerant Systems

  2015cites this paper
• Self-stabilizing Algorithms for Connected Vertex Cover and Clique Decomposition Problems

  2014cites this paper
• SMT-Based Synthesis of Distributed Self-Stabilizing Systems

  2014influential citation
• Introducing speculation in self-stabilization: an application to mutual exclusion

  2013cites this paper
• A Self-stabilizing Algorithm for Maximal p-Star Decomposition of General Graphs

  2013cites this paper
• A self-stabilizing protocol for minimal weighted dominating sets in arbitrary networks

  2013cites this paper
• A Self-Stabilizing Algorithm for Finding a Minimal Positive Influence Dominating Set in Social Networks

  2013cites this paper
• Minimising K-Dominating Set in Arbitrary Network Graphs

  2013cites this paper
• Time- and space-efficient self-stabilizing algorithms

  2012cites this paper
• Self-stabilizing Algorithm for Maximal Graph Partitioning into Triangles

  2012cites this paper
• Mariages et Trahisons

  2012cites this paper
• A Self-stabilizing Algorithm for Finding a Minimal K-Dominating Set in General Networks

  2012cites this paper
• The Byzantine Brides Problem

  2012cites this paper
• A framework for automated distributed implementation of component-based models

  2012cites this paper
• A self-stabilizing 2/3-approximation algorithm for the maximum matching problem

  2011cites this paper
• A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks

  2011cites this paper
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

  2011cites this paper
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs

  2010cites this paper
• Self-stabilizing algorithms

  2010cites this paper
• Self-Stabilizing Vertex Cover in Anonymous Networks with Optimal Approximation Ratio

  2010cites this paper
• A self-stabilizing algorithm for cut problems in synchronous networks

  2010cites this paper
• Communication Efficiency in Self-Stabilizing Silent Protocols

  2008cites this paper
• A Self-stabilizing -Approximation Algorithm for the Maximum Matching Problem

  2008cites this paper
• A Self-stabilizing Weighted Matching Algorithm

  2007cites this paper
• Project-Team Grand-Large Calcul parallèle et distribué à grande échelle

  2007cites this paper
• Communication Efficiency in Self-stabilizing Silent Protocols

  year unknowncites this paper
• Journal of Graph Algorithms and Applications an Efficient Silent Self-stabilizing 1-maximal Matching Algorithm in Anonymous Networks 60 Asada Et Al. Silent Anonymous Self-stabilizing 1-maximal Matching

  year unknowncites this paper
• Design and Management of Complex Technical Processes and Systems by Means of Computational Intelligence Methods Self-stablizing Cuts in Synchronous Networks Self-stabilizing Cuts in Synchronous Networks

  year unknowncites this paper