Error-detecting codes and fault-containing self-stabilization

Self-stabilizing algorithms recover from all cases of transient failure, bu t the mechanism of self-stabilization may be costly for mild cases of trans ient failure. Error-detecting codes can be used to identify, with high prob ability, transient faults in data. This note investigates how error-detecti ng codes can enhance self-stabilization to deal efficiently with the common case of single-process transient faults. The main results are characteriza tions of self-stabilizing algorithms that can use error-detecting codes to recover from single-process transient faults in a single step. (C) 2000 Els evier Science B.V. All rights reserved.