Time Cost Analysis of a Consensus Algorithm

. This paper describes the time analysis of Chandra & Toueg's asynchronous consensus, an algorithm of major importance in the field of fault-tolerant distributed computing. Contrary to other consensus protocols assuming semi-synchronous or synchronous conditions, Chandra & Toueg's algorithm considers an asynchronous system, thus requiring no bounds on communication delays nor on processes' speeds. Introducing an adversary model to describe the system's load, our analysis leads to the evaluation of an upper bound on the execution time of Chandra & Toueg's protocol. We compare our results concerning the asynchronous consensus with the results of former works dealing with semi-synchronous agreement algorithms. In a broader perspective, we consider this time analysis of Chandra & Toueg's consensus as a first step towards the development of specialized tools for automatic time analysis and simulation of complex agreement protocols and services in distributed computing. Keywords: Analytical..