Error-detecting codes and fault-containing self-stabilization

Self-stabilizing algorithms recover from all cases of transient failure, but the mechanism of self-stabilization may be costly for mild cases of transient failure. Error-detecting codes can be used to identify, with high probability, transient faults in data. This note investigates how error-detecting codes can enhance self-stabilization to deal efficiently with the common case of single-process transient faults. The main results are characterizations of self-stabilizing algorithms that can use error-detecting codes to recover from single-process transient faults in a single step. (C) 2000