A Transformational Approach for the Hardening of Region-Adherent Algorithms

We present new findings for a new class of fault-tolerant distributed algorithms based on a concept called region adherence. A region-adherent algorithm upper-bounds the violation of safety due to faults in space. Region adherence counter-poses the concept of self-stabilization which upper-bounds a violation of safety in time. We report on a way to systematically tighten the lower bounds of service quality known of a region-adherent algorithm. Additionally, we present a technique - which we call hardening - for transforming a region-adherent algorithm into a region-adherent algorithm that compensates n+1 times as many faults as the input algorithm where n can freely be chosen. We explain how the technique works, what its underlying concepts are, its limitations, and prove its correctness. Finally, we compare the region adherence property of a hardened algorithm with its original, un-hardened counterpart by an example, thereby quantifying the beneficial impact of the transformation.