Analyzing the Effect of Consistency Violation Faults in Self-Stabilizing Programs

Consistency violation faults \cvf{s} refer to faults that occur due to inconsistent reads in a shared memory program. In the execution of shared-memory, interleaving, self-stabilizing programs, \cvf{s} offer a trade-off. Specifically, preventing \cvf{s} requires processes to coordinate with each other thereby slowing the execution of each action. On the other hand, permitting \cvf{s} requires less coordination and faster execution of each action. However, when a \cvf occurs, it can disrupt the convergence of self-stabilizing programs. Thus, a computation of a program in the presence of \cvf{s} can be thought of as a contest where program actions attempt to take the program to a legitimate state whereas \cvf{s} could potentially this convergence. We analyze three self-stabilizing programs (token ring, coloring and maximal matching) to evaluate this contest between program transitions and \cvf{s}. We find that the relative cost of \cvf{s} is generally small, i.e., as long as a few program transitions can execute between \cvf{s}, the program (probabilistically) converges. We also find that the cost-distribution of \cvf{s} is exponential in nature in that the fraction of \cvf{s} with cost $c$ exponentially decreases with $c$. We validate these results via simulation where we control the rate of \cvf{s}.