Title :
A Transformational Approach for the Hardening of Region-Adherent Algorithms
Author :
Dilshod Rahmatov;Jan Steffen Becker;Oliver Theel
Author_Institution :
Dept. of Comput. Sci., Carl von Ossietzky Univ. of Oldenburg, Oldenburg, Germany
Abstract :
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.
Keywords :
"Systematics","Registers","Wireless sensor networks","Computational modeling","Safety","Quality of service","Fault tolerance"
Conference_Titel :
Dependable Computing (PRDC), 2015 IEEE 21st Pacific Rim International Symposium on
DOI :
10.1109/PRDC.2015.31