Preserving
Stabilization While Practically Bounding State Space Using Incorruptible
Practically Synchronized Clocks
In this paper, we
present an algorithm that transforms a stabilizing program that uses variables
with unbounded domain into a stabilizing program that uses bounded variables
and (practically bounded) physical time.
While non-stabilizing programs (that do not handle transient faults) can
deal with unbounded variables by assigning {\em large
enough but bounded} space, stabilizing programs --that need to deal with
arbitrary transient faults-- cannot do the same since a transient fault may
corrupt the variable to its maximum value.
We show that our
transformation algorithm is applicable to several problems including logical
clocks, vector clocks, mutual exclusion,
diffusing computations, and so on. Moreover, our
approach can also be used to bound counters used in an earlier work by Katz and
Perry for adding stabilization to a non-stabilizing program.
By combining our algorithm with that work by Katz and Perry, it would be
possible to provide stabilization for a rich class of problems, by assigning {\em large enough but bounded} space for variables.
Paper:
Return to the publication list
Return to the Sandeep's home page