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

08/21/2021
by   Sandeep S. Kulkarni, et al.
0

Consistency violation faults 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, s offer a trade-off. Specifically, preventing s requires processes to coordinate with each other thereby slowing the execution of each action. On the other hand, permitting s requires less coordination and faster execution of each action. However, when a occurs, it can disrupt the convergence of self-stabilizing programs. Thus, a computation of a program in the presence of s can be thought of as a contest where program actions attempt to take the program to a legitimate state whereas 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 s. We find that the relative cost of s is generally small, i.e., as long as a few program transitions can execute between s, the program (probabilistically) converges. We also find that the cost-distribution of s is exponential in nature in that the fraction of s with cost c exponentially decreases with c. We validate these results via simulation where we control the rate of s.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset