Browsing by Author "Chattopadhyay, Subhendu"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Dynamic and self-stabilizing distributed matching
    (2003) Chattopadhyay, Subhendu; Higham, Lisa
  • Thumbnail Image
    ItemOpen Access
    Dynamic and Self-stabilizing Distributed Matching
    (2003-01-28) Chattopadhyay, Subhendu; Higham, Lisa; Seyffarth, Karen
    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.