Probabilistic verification of a synchronous round-based consensus protocol

TitleProbabilistic verification of a synchronous round-based consensus protocol
Publication TypeConference Papers
Year of Publication1997
AuthorsDuggal HS, Cukier M, Sanders WH
Date Published1997/10//
Keywordsbusiness-critical applications, consensus protocol correctness, crash failures, formal verification, network environment, probabilistic verification, probabilities, probability, program verification, proper behavior, protocol behavior, Protocols, realistic environment, reliable distributed systems, safety-critical applications, simple consensus protocol, software reliability, stochastic assumptions, synchronous round based consensus protocol, synchronous round based consensus protocols, traditional proof techniques

Consensus protocols are used in a variety of reliable distributed systems, including both safety-critical and business-critical applications. The correctness of a consensus protocol is usually shown, by making assumptions about the environment in which it executes, and then proving properties about the protocol. But proofs about a protocol's behavior are only as good as the assumptions which were made to obtain them, and violation of these assumptions can lead to unpredicted and serious consequences. We present a new approach for the probabilistic verification of synchronous round based consensus protocols. In doing so, we make stochastic assumptions about the environment in which a protocol operates, and derive probabilities of proper and non proper behavior. We thus can account for the violation of assumptions made in traditional proof techniques. To obtain the desired probabilities, the approach enumerates possible states that can be reached during an execution of the protocol, and computes the probability of achieving the desired properties for a given fault and network environment. We illustrate the use of this approach via the evaluation of a simple consensus protocol operating under a realistic environment which includes performance, omission, and crash failures