Thumbnail
Access Restriction
Open

Author Chattopadhyay, Subhendu ♦ Higham, Lisa ♦ Seyffarth, Karen
Source CiteSeerX
Content type Text
Publisher ACM
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Description Self-stabilization is a unified model of fault tolerance. A self-stabilizing system can recover from an arbitrary transient fault without re-initialization. Self-stabilization is a particularly valuable at-tribute of distributed systems since they are typically prone to various faults and dynamic changes. In several distributed applications, pairing of processors connected in a network can be viewed as a matching of the underlying graph of the network. A self-stabilizing matching algorithm can be used to build fault tolerant paring of clients and servers connected in a network. First contribution of this report is an efficient, dynamic and self-stabilizing maximal matching algorithm for arbitrary anonymous networks. The algorithm implements a locally distinct label generation technique that can be used by other applications. The second contribution of this report is a dynamic and self-stabilizing maximum matching algorithm for arbitrary bipartite networks. This is the first distributed maximum matching algorithm for networks containing cycles. Chapter 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2002-01-01
Publisher Institution In Principles of Distributed Computing (PODC), 21st Ann. Symp