We present an on-line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Our algorithm is deadlock free, and with k failures maintains at least M - k matching pairs during the reconfiguration process, where M is the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst-case reconfiguration time is O(k min(|A|, |B|)) after k failures, where A and B are the node sets, but simulations show that the average-case reconfiguration time is much better. The algorithm is also simple enough to be implemented in hardware.

This technical report has been published as

Maintaining Bipartite Matchings in the Presence of Failures. Edwin Hsing-Mean Sha and Kenneth Steiglitz,

Proc. of 7th Internat. Parallel Processing Symposium, April 13-16, 1993, Newport Beach, California.

Networks, 23(5), pp. 459-471, August 1993.