Probabilistic Guarantees on the Termination Time of a Consensus Algorithm in Asynchronous Systems

Probabilistic Guarantees on the Termination Time of a Consensus Algorithm in Asynchronous Systems N. Sergent This paper is concerned with an application of Hierarchical Coloured Timed Petri Nets to the modelling and the performance evaluation of a distributed consensus algorithm. The asynchronous system model is augmented with Failure Suspectors, which allow to overcome the impossibility of reaching consensus in the presence of crash failures. We have used a top down modular approach to manage the complexity of the considered protocols. The termination time of the consensus algorithm is determined by the communications cost, i.e. by the timing characteristics of the network used for exchanging messages. Our model establishes a strong interdependence between the end-to-end delays and the amount of traffic on the network. As a network protocol we have considered UDP/IP. Simulating the consensus Petri net model, it is possible to obtain optimal values for the Failure Suspectors parameters. Probabilistic guarantees on the termination time of consensus are provided.