Please use this identifier to cite or link to this item:
|Title:||Dynamic and Self-stabilizing Distributed Matching|
|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.|
|Appears in Collections:||Higham, Lisa|
Files in This Item:
|2002-704-07.pdf||303.75 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.