Analyzing leader election protocol by probabilistic model checking

摘要

This paper presents a quantitative analysis of Itai's leader election algorithm using probabilistic model checking. In particular, a leading probabilistic model checker PRISM is utilized to simulate the algorithm executions. From performance analysis perspective, this paper investigates execution efficiency of this algorithm. Properties to be considered is the expected round of leader election under certain situations. Moreover, as an important performance concern, energy consumption is also simulated in the experiment. This paper also extends the assumptions of the original algorithm to study the performance over unreliable channels. Experimental results show that for certain number of processes, the algorithm will terminate with probability 1. Conclusion can also be drawn that the reliability of channels does have great effect on the performance of this algorithm. In order to achieve better performance, it is a better choice to decrease the number of process in the election and extend the choice scope for each process.