EARLY CONSENSUS IN AN ASYNCHRONOUS SYSTEM WITH A WEAK FAILURE DETECTOR

Consensus is one of the most fundamental problems in the context of fa ult-tolerant distributed computing. The problem consists, given a set Omega of processes having each an initial value vi, in deciding among Omega on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject to a single process crash. In 1991, Chandra and Toueg showed t hat, by augmenting the asynchronous system model with a well defined u nreliable failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the lozenge l failure detect or. In this paper we propose a new consensus algorithm, also using the lozenge l failure detector, that is more efficient than the Chandra-T oueg consensus algorithm. We measure efficiency by introducing the not ion of latency degree, which defines the minimal number of communicati on steps needed to solve consensus. The Chandra-Toueg algorithm has a latency degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication steps (latency degree of 7). We believe that this is an interesting re sult, which adds to our current understanding of the cost of consensus algorithms based on lozenge l.