Workshop do Projeto ARGO

Workshop do Projeto ARGO – Junho/2001

Consensus in One Communication Step

^{1Francisco Brasileiro, ²Fabíola Greve*
, ²Achour Mostefaoui, ²Michel Raynal]

^{1Universidade Federal da Paraíba (UFPB)
fubica@dsc.ufpb.br

^{2IRISA, Université de Rennes 1
{fgreve | achour | raynalg}@irisa.fr

Introduction

The Consensus problem is now recognized as being one of the most important problems to solve when one has to design or to implement reliable applications on top of an unreliable asynchronous distributed system. Informally, the Consensus problem is defined in the following way. Each process proposes a value, and all non-crashed processes have to agree on a common value which has to be one of the proposed values. To converge towards a single decided value, a consensus protocol makes the processes exchange proposed values. Each exchange constitutes a communication step. So, an interesting measure of the efficiency of a protocol is the number of communication steps it requires. In the best scenario, the consensus protocols proposed so far require that processes execute at least two communication steps.}}}

This paper presents a novel and surprisingly simple consensus protocol that allows processes to decide in a single communication step when "enough" processes propose the same value. "Enough" means at least (n - ¦ ), where n is the number of processes and ¦ is the maximum number of them that can be faulty. This protocol requires ¦ < n/3. Although failures do occur, they are rare in practice. This observation shows that the ¦ < n/3 requirement is not really constraining.

The Protocol

Underlying Principle The idea that underlies the design of the protocol is very simple. It comes from the following observation: if all the processes initially propose the same value, then this value is necessarily the decided value, whatever the protocol and the system behavior. Hence, the proposed protocol executes a first communication step during which the processes exchange the values they propose. Then, each process checks whether all the processes have the same initial value (actually, (n - ¦ ) identical values are sufficient). If it is the case, this value is decided. If it is not, the underlying protocol is used.

The Protocol The protocol is described in Figure 1. A process p_i starts a Consensus execution by invoking Consensus(n _i). It terminates it when it executes the statement return which provides it with the decided value (at line 4, 7 or 9). To prevent a process from blocking forever (i.e., waiting for a value from a process that has already decided), a process that decides, uses a reliable broadcast to disseminate its decision value. To this end the Consensus function is made of two tasks, namely, T1 and T2. T1 implements the core of the protocol. Line 4 and T2 implement the reliable broadcast.

Function Consensus(n _i)

Task T1:

(1) broadcast proposed(n _i);

(2) wait until ((n - ¦ ) proposed messages have been received);

(3) if (these messages carry the same estimate value n )

(4) then broadcast decision(n ); return(n )

(5) else if ((n - 2¦ ) proposed messages carry the same value n )

(6) then n _i ¬ n endif;

(7) return(Underlying_Consensus(n _i))

(8) endif

Task T2:

(9) upon reception of decision(n ): broadcast decision(n ); return(n )

Fig. 1. The Consensus Protocol

One Communication Step Decision Let us consider the case where all the processes that propose a value (those are the processes that have not initially crashed) propose the same value. The protocol makes the processes that do not crash decide in exactly one communication step. It is important to notice that, in the same situation, no other protocol presented in the literature allows a one step decision.

If less than (n - ¦ ) processes propose the same value n , then the consensus is solved by the Underlying_Consensus protocol. When there is a set of (n - ¦ ) processes that propose the same value n , there are two cases according to the set of proposed messages received by a process p_i at line 2:

Case 1: The (n - ¦ ) proposed messages received by p_i carry n . It follows from lines 2-4 that p_i decides after one communication step.

Case 2: One of the (n - ¦ ) proposed messages received by p_i carries a value different from n . Let us notice that, as there are (n - ¦ ) proposed messages carrying n and 3¦ < n, it follows that necessarily p_i receives at least (n - 2¦ ) proposed messages carrying n , and consequently adopts n at line 6. It follows that when (n - ¦ ) processes propose the same value n , all the processes that do not decide at line 4, invoke Underlying_Consensus with same value n . Interestingly, some consensus protocols expedite the decision when processes propose the same value.