Analyzing dynamic voting using Petri nets

Dynamic voting is considered a promising technique for achieving high availability in distributed systems with data replication. To date, stochastic analysis of dynamic voting algorithms is restricted to either site or link Markov models, but not both, possibly because of the difficulty in specifying the state-space which grows exponentially as the number of sites increases. Furthermore, to reduce the state-space, the assumption of “frequent updates” was normally made, which results in an overestimation of the availability. In this paper, we develop a Petri net model that considers both site and link failures and also relaxes the modeling assumption of frequent updates. We test our Petri net model on ring and star network topologies to analyze if availability under dynamic voting can be seriously degraded if updates are not frequent under various site and link failure/repair situations. Finally, We use the Petri net developed in the paper to determine the maximum achievable improvement in availability when null updates are introduced to augment regular updates to keep the status of availability up-to-date