Preserving Stabilization While Practically Bounding State Space
Vidhya Tekken Valapil, Sandeep S. Kulkarni · 2017
Stabilization is a key dependability property for dealing with unanticipated transient faults, as it guarantees that even in the presence of such faults, the system will recover to states where it satisfies its specification. One of the desirable attributes of stabilization is the use of bounded space for each variable.In this paper, we present an algorithm that transforms a stabilizingprogram that uses variables with unbounded domain into astabilizing program that uses bounded variables and (practicallybounded) physical time. While non-stabilizing programs (that donot handle transient faults) can deal with unbounded variables byassigning large enough but bounded space, stabilizing programs-that need to deal with arbitrary transient faults- cannot dothe same since a transient fault may corrupt the variable to itsmaximum value.We show that our transformation algorithm is applicable toseveral problems including logical clocks, vector clocks, mutualexclusion, leader election, diffusing computations, Paxos basedconsensus, and so on. Moreover, our approach can also be usedto bound counters used in an earlier work by Katz and Perry foradding stabilization to a non-stabilizing program. By combiningour algorithm with that earlier work by Katz and Perry, it wouldbe possible to provide stabilization for a rich class of problems, by assigning large enough but bounded space for variables.