Title :
A robust distributed generalized matching protocol that stabilizes in linear time
Author :
Goddard, Wayne ; Hedetniemi, Stephen T. ; Jacobs, David P. ; Srimani, Pradip K.
Author_Institution :
Dept. of Comput. Sci., Clemson Univ., SC, USA
Abstract :
We present a self-stabilizing algorithm for finding a generalized maximal matching (b-matching) in an arbitrary distributed network. We show that the algorithm converges in O(m) moves under an unfair central demon independent of the b-values at different nodes. The algorithm is capable of working with multiple types of demons (schedulers) as is the most recent algorithm in [1, 2].
Keywords :
computational complexity; computer networks; distributed algorithms; optimisation; protocols; b-matching; distributed network; generalized maximal matching; robust distributed generalized matching protocol; self-stabilizing algorithm; Bandwidth; Computer science; Costs; Delay; Fault tolerant systems; Intelligent networks; Jacobian matrices; Protocols; Robustness; Scheduling algorithm;
Conference_Titel :
Distributed Computing Systems Workshops, 2003. Proceedings. 23rd International Conference on
Print_ISBN :
0-7695-1921-0
DOI :
10.1109/ICDCSW.2003.1203595
