Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45979
Title: Dynamic and Self-stabilizing Distributed Matching
Authors: Chattopadhyay, Subhendu
Higham, Lisa
Seyffarth, Karen
Keywords: Computer Science
Issue Date: 28-Jan-2003
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.
URI: http://hdl.handle.net/1880/45979
Appears in Collections:Higham, Lisa

Files in This Item:
File Description SizeFormat 
2002-704-07.pdf303.75 kBAdobe PDFView/Open
2002-704-07.ps357.03 kBPostscriptView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.