A Robust Distributed Generalized Matching Protocol that Stabilizes in Linear Time

Wayne Goddard; Stephen T. Hedetniemi; David P. Jacobs; Pradip K. Srimani

doi:10.1109/ICDCSW.2003.1203595

23rd International Conference on Distributed Computing Systems Workshops, 2003. Proceedings.

A Robust Distributed Generalized Matching Protocol that Stabilizes in Linear Time

Year: 2003, Pages: 461

DOI Bookmark: 10.1109/ICDCSW.2003.1203595

Authors

Wayne Goddard, Clemson University
Stephen T. Hedetniemi, Clemson University
David P. Jacobs, Clemson University
Pradip K. Srimani, Clemson University

Abstract

We present a self-stabilizing algorithm for .nding a generalized maximal matching (b-matching) in an arbitrary distributed network. We show that the algorithm converges in 0(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].

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!

Designing Scalable b-MATCHING Algorithms on Distributed Memory Multiprocessors by Approximation
SC16: International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
Improved scheduling of generalized pinwheel task systems
Proceedings Fourth International Workshop on Real-Time Computing Systems and Applications
Fault Tolerant Distributed Coloring Algorithms that Stabilize in Linear Time
Parallel and Distributed Processing Symposium, International
Faster algorithms for the generalized network flow problem
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
Nested Emptiness Search for Generalized B?chi Automata
Proceedings. Fourth International Conference on Application of Concurrency to System Design, 2004. ACSD 2004.
Third order matching is decidable
1992 Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science
Linear stereo matching
2011 IEEE International Conference on Computer Vision (ICCV 2011)
Improved FFD B-Spline Image Registration
2007 11th IEEE International Conference on Computer Vision
Generalized Shuffled Linear Regression
2021 IEEE/CVF International Conference on Computer Vision (ICCV)
Deep Generalized Unfolding Networks for Image Restoration
2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)

A Robust Distributed Generalized Matching Protocol that Stabilizes in Linear Time

Authors

Abstract

Related Articles