We present an on-line distributed reconfiguration algorithm for findin
g a new maximum matching incrementally after some nodes have failed. O
ur algorithm is deadlock-free and, with k failures, maintains at least
M - k matching pairs during the reconfiguration process, where M is t
he size of the original maximum matching. The algorithm tolerates fail
ures that occur during reconfiguration. The worst-case reconfiguration
time is O(k min(Absolute value of A, Absolute value of B)) after k fa
ilures, where A and B are the node sets, but simulations show that the
average-case reconfiguration time is much better. The algorithm is al
so simple enough to be implemented in hardware. (C) 1993 by John Wiley
& Sons, Inc.