Dynamic and Self-stabilizing Distributed Matching
Date
2003-01-28
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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 attribute of
distributed systems since they are tipically 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 pairing of clients and servers connected in a network. First
contribution of this report is an efficient, dynamic and self-stabilizing
mazimal 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 alrogithm for arbitrary biparite networks.
This is the first distributed amximum matching algorithm for networks
containing cycles.
Description
Keywords
Computer Science