Dariusz R Kowalski
email: d.kowalski@liverpool.ac.uk

Achour Mostéfaoui
email: achour@irisa.fr

Synchronous Byzantine Agreement with Nearly a Cubic Number of Communication Bits

Keywords: Agreement problem, Byzantine process, Consensus, Synchronous distributed system, Message-passing model, Round-based protocol, EIG

.

 were the first and only who solved the problem by using a polynomial number of communication bits, for the whole optimal range t < n/3 of the number of Byzantine processes and within the optimal number (t + 1) of communication rounds. Their solution, though very complex and sophisticated, requires processes to send O(n 9 ) bits in total.

In this work, we present much simpler solution that also holds for the whole optimal range t < n/3 and the optimal number t + 1 of communication rounds, and at the same time lowers the number of exchanged communication bits to O(n 3 log n). For achieving such an improvement, processes no more exchange relayed proposed values, but information on suspicions "who suspects who", the size of which is quadratic in n in the worst case.

Introduction

The Consensus problem is considered as a fundamental problem in fault-tolerant distributed systems. In case processes can exhibit a malicious behavior, the obtained variant of consensus is often called Byzantine Agreement. In order to assure perfect reliability, deterministic solutions are of utmost importance for this problem, and this is also the focus of this paper; for recent advances and references to the area of randomized solutions we refer the reader to the work by King and Saia [START_REF] King | Breaking the O(n 2 ) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary[END_REF] and by Aspnes [START_REF] Aspnes | Faster randomized consensus with an oblivious adversary[END_REF].

The first and the simplest designed deterministic algorithm for the synchronous distributed computing model is the exponential information gathering protocol (from now on called EIG protocol) based on a tree construction proposed by Bar-Noy, Dolev, Dwork and Strong [START_REF] Bar-Noy | Shifting Gears: Changing Algorithms on the Fly To Expedite Byzantine Agreement[END_REF] as a simple reformulation of the original protocol proposed by Pease, Shostak and Lamport in 1980 [START_REF] Pease | Reaching Agreement in Presence of Faults[END_REF]. The algorithm requires processes to send exponentially long messages and performs exponentially many local computation steps, in terms of the number n of processes. Many researchers have since tried to reduce the cost of the solution, However most of them either lowered the maximal range of the tolerated number of faulty processes t from t < n/3 (the upper bound) to some smaller values [START_REF] Dolev | Early Stopping in Byzantine Agreement[END_REF][START_REF] Moses | Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time[END_REF][START_REF] Berman | Efficient Distributed Consensus with n = (3+ )t Processors. 5th International Workshop on Distributed Algorithms (WDAG'91)[END_REF] or increased the maximum number of rounds needed in the worst case to terminate (the lower bound being t + 1) [START_REF] Bar-Noy | Shifting Gears: Changing Algorithms on the Fly To Expedite Byzantine Agreement[END_REF][START_REF] Dolev | An Efficient Algorithm for Byzantine Agreement without Authentication[END_REF][START_REF] Toueg | Fast Distributed Agreement[END_REF]. For such a purpose, they developed a series of techniques to exploit the redundancy encountered in the tree structure of the EIG protocol, sacrificing the optimum fault-tolerance or the minimum number of communication rounds. [START_REF] Bar-Noy | Shifting Gears: Changing Algorithms on the Fly To Expedite Byzantine Agreement[END_REF][START_REF] Coan | A Communication-Efficient Canonical Form for Fault-Tolerant Distributed Protocols[END_REF] propose a trade-off between the number of rounds and the bit complexity for any constant d they increase the number of rounds to t + t/d while decreasing the bit complexity to O(n d ). Similarly, [START_REF] Berman | Efficient Distributed Consensus with n = (3+ )t Processors. 5th International Workshop on Distributed Algorithms (WDAG'91)[END_REF] proposes a trade-off between the resilence of the protocol and the bit complexity for any constant the ration of faulty processes is increased to (3 + )t while the bit complexity is lowered to poly(n) • O(2 1/ ).

Garay and Moses [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF] were the first and only who solved the problem with polynomial number of communication bits and polynomial local computation cost, still meeting both the bound of t < n/3 on the number of Byzantine processes and the number of t+1 communication rounds. Their solution is very complex, and both polynomials are actually large -according to our estimates they are both O(n 9 ) -thus leaving a huge space for improvement. The only known lower bound Ω(nt) on the number of communication bits was proved by Dolev and Reischuk [START_REF] Dolev | Bounds on Information Exchange for Byzantine Agreement[END_REF]; this bound becomes Ω(n 2 ) for linear number of Byzantine processes. The bound t < n/3 on the number of Byzantine processes necessary for reaching consensus was given by Lamport, Shostak and Pease [START_REF] Lamport | The Byzantine Generals Problem[END_REF]. Fisher and Lynch [START_REF] Fisher | A lower Bound for the Time to Assure Interactive Consistency[END_REF] proved the lower bound (t + 1) on the number of communication rounds, which holds even for milder process failures such as crashes. The interested reader can find in [START_REF] Garay | Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds[END_REF] the history of the improvements introduced from the initial protocol in 1980 [START_REF] Pease | Reaching Agreement in Presence of Faults[END_REF] to the polynomial one in 1998 [START_REF] Garay | Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds[END_REF] (the full version of [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF]). We are not aware of any improvements since then.

The table below taken from [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF] gives an overview of the most important improvment over time concerning the consensus problem. Other improvments occured but they consider randomization; King and Saia [START_REF] King | Breaking the O(n 2 ) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary[END_REF] reduced the bit complexity to sub-quadratic.

Protocol n rounds comm. bits PSL 1980 [START_REF] Pease | Reaching Agreement in Presence of Faults[END_REF] 3t + 1 t + 1 exp(n) DFFLS,TPS 1982 [START_REF] Dolev | An Efficient Algorithm for Byzantine Agreement without Authentication[END_REF][START_REF] Toueg | Fast Distributed Agreement[END_REF] 3t + 1 > 2t poly(n) C 1985 [START_REF] Coan | A Communication-Efficient Canonical Form for Fault-Tolerant Distributed Protocols[END_REF] 4t [START_REF] Moses | Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time[END_REF] 6t + 1 t + 1 poly(n) BGP 1989 [START_REF] Berman | Towards Optimal Distributed Consensus (Extended Abstract)[END_REF] 4t + 1 t + 1 poly(n) BG 1991 [START_REF] Berman | Efficient Distributed Consensus with n = (3+ )t Processors. 5th International Workshop on Distributed Algorithms (WDAG'91)[END_REF] (

+ 1 t + t/d O(n d ) BD,DRS 1986 [2, 11] Ω(t 2 ) t + 1 poly(n) BDDS 1987 [3] 3t + 1 t + t/d O(n d ) MW 1988
+ )t t + 1 poly(n)O(2 3
/ ) GM 1993 [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF] 3t

+ 1 t + 1 O(n 9 ) This paper 3t + 1 t + 1 O(n 3 log n)
Our result In this work, we present a solution that is simpler yet more efficient in terms of communication complexity than the best known deterministic solution by Garay and Moses [START_REF] Garay | Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds[END_REF].

In particular, it matches the two bounds: t < n/3 on the number of tolerated Byzantine processes, and t + 1 on the number of communication rounds, while the total number of communication bits O(n 3 log n) sent by non-Byzantine processes is close by factor O(n log n) to the lower bound Ω(n 2 ) on the total number of communication bits. In order to achieve this, the processes do not exchange the values they received in the previous rounds, but instead, they exchange a "digest" on the information they received. Based on these digests, they locally maintain information of "who suspects who" during each round. Thanks to this technique, the size of the exchanged information much reduced compared to former works, and the crucial part of the analysis shows that this very limited information is still sufficient to "mimic" the evaluation procedure done by the original EIG protocol "in spirit". It needs to be said that the evaluation made by our algorithms, based on very limited information exchange, might be slightly different than the evaluation made by the original EIG algorithm executed against the same adversarial schedule, but similar mechanisms guarantee agreement and validity of the final evaluation throughout correct nodes.

EIG protocol vs. our approach The EIG protocol works in two phases. During the first phase, processes exchange messages during t+1 communication rounds. At each round each process forwards all the information it received in the previous round to all processes. This protocol can be seen as the fully informed protocol, and hence it results in super-exponential communication complexity (understood as the number of exchanged bits). The collected information is stored in tree-like data structures, to which we refer as evaluation trees. At the end of round t + 1, the second phase (local computation on the local trees) is started. It consists of a bottom-up computation on each of the collected trees (one per process), where a resolved value is associated to each node of the tree structure by applying a resolution function to the children of this node. The decision value of the process is the resolved value associated with the set of roots of the trees. The polynomial protocol by Garay and Moses [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF] uses the same tree structures, though parts of the trees are cut using sophisticated techniques. One of the introduced techniques consists in detecting cheating processes (Byzantine processes) in a given round in order to prevent them from cheating in subsequent rounds.

Our protocol is similar to the EIG protocol in its way of proceeding, as processes exchange information during (t + 1) rounds and store the information they receive in local data structures. The fundamental difference is in the nature of the stored data. Instead of storing proposed values and then arrays of received values, arrays of arrays of received values, etc., the processes exchange only a relatively small digest of received information. More precisely, each process manages an array of process ids of size n, where it stores the ids of processes it itself suspects to be Byzantine. At the end of each round this information is updated and the new array is sent to all processes in the next round. Moreover, in order to detect cheating processes, a classical confirmation mechanism is used. All information broadcast by a process during a round is echoed by each receiving process to all other processes (the same mechanism is used for the consistent broadcast of Bracha and Toueg [START_REF] Bracha | Resilient Consensus Protocols[END_REF]). A message sent at a round r is confirmed at some process p i at the end of round r + 1 and its sender in consequently not suspected if the same copy is relayed to p i by at least (n -t) processes during round r + 1. Conversely, if the message of some process is not confirmed in the next round, the sender is suspected. The fact that processes exchange suspicion arrays prevents the size of the exchanged information from exponential growth. To ease the presentation of our algorithm, we assume that the suspicion information is stored in a data structure similar to the EIG tree, although the size of the information sent by each correct process during each round is only quadratic in the number n of processes. In the remainder, we proceed as follows. In Section 2 we introduce the model and the consensus problem in more details. Section 3 presents the EIG tree structure used by the EIG original protocol and almost all other protocols that meet the t < n/3 bound. Section 4 describes the main algorithm. The analysis of the algorithm is split into two sections: the correctness proof of the protocol is given in Section 5, and the complexity measures are given in Section 6.

Byzantine Agreement and Computation Model

In this paper, we consider the classical Byzantine distributed synchronous message-passing model. The system is composed of a set Π of n synchronous processes, with ids in {1, . . . , n}, which communicate through a reliable synchronous point to point channels (there is an a priori known bound on both message transfer delays and local computation of processes). Moreover, up to t processes can exhibit a Byzantine behavior, which means that such a process can behave in an arbitrary manner. This is the most severe process failure model: a Byzantine process can crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, send different values to different processes, perform arbitrary state transitions, etc. A process that exhibits a Byzantine behavior during an execution is called faulty. Otherwise, it is called correct.

In the Byzantine Agreement problem, also called Consensus, each process p i proposes an initial value v i (this can be any value). Contrarily to many previous works including the only polynomial solution of Garay and Moses [START_REF] Garay | Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds[END_REF] that restrict the set of proposable values to {0, 1} (called binary consensus, only two different values are proposable), we consider multivalued consensus.

The goal for each (correct) process is to decide on a value. A Byzantine agreement protocol has to satisfy the following three properties:

In this paper we consider deterministic synchronous round-based algorithms. Moreover, we do not use authentication (public key asymmetric cryptography to sign messages). During a round, each correct process may send to all processes, including itself, a unique message whose content is specified by the executed algorithm, and all messages are received within the same round. Then each process performs some local computation before starting a new round, or it decides and terminates.

The efficiency of algorithms is measured by the number of communication rounds (optimally t + 1), and the number of bits sent in messages by correct processes (for which the known lower bound is Ω(n2 )). Fault tolerance of algorithms is measured by the number of Byzantine processes that can be tolerated -ideally any number t < n/3.

The EIG Tree Structure

The exponential information gathering tree (EIG tree) is a data structure used to recording the information received by a given process along the successive rounds of an n-process round-based distributed computation. This structure is costly to maintain, as its number of nodes is exponential in the number n of processes. The trees we consider have (at the end of the t + 1 rounds of the execution) exactly t + 2 levels (from 0 to t + 1). 2 A node of level has exactly n -children and has a label that consists of an element string of process ids (a process id appears at most once in a given label). The root of this tree is labeled with an empty string λ. The set of labels of the EIG tree is the set of all possible strings of size at most t + 1, hence the size of the tree. Figure 1 presents an example of an EIG tree associated with some process p i . We consider in this example a number of processes n greater than 5 but we cannot represent the whole tree. One can see that starting from level 1, and for the sake of clarity, many nodes are not represented and are replaced by (• • • ).

During the execution of the original EIG protocol, each node x of the tree is used to store two values: val(x) and newval(x). The value of val(x) of a node x on level is assigned during round . It is the -th hand report of some initial value (i.e., received through the chain of processes represented by the ids constituting the label of node x). The value newval(x) of a node x is assigned during the decision procedure after the t + 1 rounds.

The Main Algorithm

The proposed protocol proceeds in t + 1 synchronous rounds, similarly to the EIG protocol. During a round r, each process sends a same message to all other processes (sending phase), next it waits for the messages sent to it (reception phase), and then it does local computation on both received and locally stored data. The fundamental difference between our solution and the EIG algorithm, as mentioned earlier, is in the nature of the stored and sent data. In other words, we use the same EIG tree structure that is decorated in a different way. Instead of storing the proposed values and then the arrays of received values, the arrays of arrays of received values, etc., kept in the exponential size EIG tree structure, the processes maintain and exchange only a digest of received information. More precisely, during the first two rounds, processes exchange proposed values (similarly to the EIG protocol). Then, starting from the third round, each process informs the other processes which processes it is sure are Byzantine.

To ease the presentation of our algorithm, we say that a correct process p c received a default value ⊥, which cannot be proposed to the consensus, from a Byzantine process p b , when process p c received no value, or it received a non well-formed message, or if it has itself suspected p b as being Byzantine in a previous round.

The two basic ideas that underlie and distinguish the proposed approach from previous works are: the exchange of suspicion information (except for the first two rounds) instead of the proposed values or the whole history of messages, and the use of the echo mechanism (here, called a confirmation mechanism) introduced by Bracha and Toueg [START_REF] Bracha | Resilient Consensus Protocols[END_REF] for asynchronous systems. A message can be safely delivered (we say here that it is confirmed) if it has been echoed by at least (n-t) different processes. Bracha and Toueg proved that this mechanism ensures that if a correct process confirms a value from a given process at some round, no other correct process can confirm a different value from the same process at the same round (either it confirms the same value or no value at all). Moreover, values broadcast by correct processes are always confirmed (safely delivered) by at least all correct processes. They proved that in order to implement this mechanism, it is necessary to have t < n/3.

During a round r, r ≥ 3, each process broadcasts a message that contains two parts. The first part is the data that the process wants to disseminate, called main information or main part of a message, and the second part consists of the main information the process has received from each process in the previous round. This second part is called the proof by Bracha and Toueg [START_REF] Bracha | Resilient Consensus Protocols[END_REF]; we call it the echo, due to its nature, and it will serve to confirm the main information of the previous round. A main information received from a given process p j at round r is confirmed to a process p i at round r + 1 if it has been echoed to p i (i.e., forwarded in the echo part of messages at round r + 1) by at least (n -t) different processes.

In the algorithm description below, we only specify the behavior of correct processes, as Byzantine processes, due to their malicious nature, are not bounded by the rules of the algorithm.

Principles of the Algorithm

Each process maintains two data structures: an EIG tree to store received values, and a set byz (initialized to ∅) to store the ids of the processes it suspects to be Byzantine (it suspects by itself, not as reported by some other process). Similarly to the original EIG protocol, each node of the EIG tree with label x can store values (noted val(x) and newval(x) in the original EIG protocol). In the present paper, each node stores three: values val(x) and cval(x), representing respectively the main part and the echo part of messages, and newval(x) assigned to node x in the decision procedure at the end of round t + 1. newval(x) can be seen as a correction of val(x). The values val(x) and cval(x) are collected during the different rounds, and newval(x) is set during the extraction of the decision value after the t + 1 rounds. In the presentation of the algorithm, when we say that we decorate node x, we mean that the variables val(x) and cval(x) associated with the node labeled x are set to some values (except of nodes x on level 1, for which cval(x) is not defined).

The following algorithm describes the execution of the protocol from the point of view of a correct process p i and shows how this process manages its two data structures: the EIG tree and the set byz i .

Round 1. Each process sends its initial value to all other processes; this is the main part of the message and there are no echoes in this round. The variable val(x) will be set during the next round. Moreover, during the computation phase of round 2 (after the confirmation checking of the messages sent during the first round), a correct process p i adds to its set byz i of suspected Byzantine processes any process p b whose initial value (the one it received directly from p b at round 1) is not confirmed at round 2.

Round 3. Each process p i attaches its local set byz i of Byzantine processes as the main part of its message (the "digest"), and echoes the arrays of initial values it received during round 2 (i.e., up to n arrays of n values each).

Here we can see a difference from the original EIG protocol. During a round r, 3 ≤ r ≤ t + 1, a correct process not only decorates the nodes of level r but also possibly the nodes from level r -1 to level t + 1. Indeed, the confirmation mechanism needs two rounds to detect Byzantine behaviors and once we uncovered a Byzantine process, of course we never rely on what she says. For example, if p j behaved in a Byzantine way (e.g., sending different values to different correct processes) during round 1, it will be suspected by at least one correct process p k at the latest at the end of round 2 (using the confirmation mechanism). Then, p k sends the information "p k suspects p j " to the other processes at round 3. We will see below how the variables val(x) and cval(x) associated with the different nodes x are set. Finally, p i enriches its list of Byzantine processes using the confirmation mechanism applied to the messages received in the previous round and echoed in this round.

Round r, 4 ≤ r ≤ t + 1. Starting from round 4, rounds are the same as for round 3, except that the messages sent by the different processes include the list of Byzantine processes as the main part of the message, and echo the lists received during the previous round in the echo part (the proposed values are no more sent). We will define below how the variables val(x) and cval(x) associated with the different nodes x are set in these rounds.

Once the t+1 rounds are terminated, the EIG tree is decorated as follow. Recall that we already showed how to define val(v) for any node x on level 1 of the tree, and also the values cval(x) for nodes on level 2. In the following, we decorate the EIG tree with two values and ⊥. The value means "do not suspect" whereas the value ⊥ means "suspect". For example, when val(x) of some node x = yjk is set to , this means that p k reported that it suspects p j , and when cval(x) of some node x = yjk is set to , this means that p reported that p k does not suspect p j (this is a second-hand information -an echo).

• For each node x from a level greater than 1 and at most t, x = yk where y is a string (possibly empty) of ids and k, are ids of two other processes not listed in y: p i sets val(x) to if p never reported to p i by round t that it suspects p k ; otherwise, val(x) is set to ⊥.

• For each node x from a level greater than 2, x = yjk where y is a string (possibly empty) of ids and j, k are ids of two other processes not listed in y: p i sets cval(x) to if p never reported by round t + 1 to p i that p k reported that it suspects p j (this value is reported in the second-hand information included in the echo part of the message received by p i from p ); otherwise, cval(x) is set to ⊥.

• One can note that for the nodes of level t + 1 (i.e., the leaves of the EIG tree), the variable val(x) is set to no value, so for each leaf node x, x = yk where y is a string (possibly empty) of ids and k, are ids of two other processes not listed in y: p i sets val(x) to if p did not report to p i that it suspects p k ; otherwise, val(x) is set to ⊥.

Remark 1: Note that, except for the third round, the echoes are not themselves echoed. This however does not influence the later evaluation and decision making, since similarly to the EIG protocol, there is high redundancy in the received information and some of it can be skipped, as pointed out in many previous works including [START_REF] Garay | Fully polynomial Byzantine agreement in t + 1 rounds[END_REF]. Moreover, from round to round, the number of nodes in subsequent levels of the constructed EIG tree grows, whereas the new available information (main part of received messages) remains quadratic. This means that all the collected information can be stored in arrays instead of the EIG tree structure. The tree is however used to ease the presentation of the decision making and its analysis.

Extracting the final decision value

As for the EIG protocol, the decision making consists in assigning new values to the nodes of the EIG tree of each correct process, starting from the leaves (bottom-up evaluation). Let x be a node of the tree and val(x) and cval(x) be the values with which node x is decorated. The evaluation mechanism of the nodes consists in assigning a new value newval(x) to each node x, the new value of the root being the decision value. Let us consider the EIG tree of a correct process p i .

• When x is a leaf, newval(x) ← val(x). This will be one of or ⊥.

• When x is an internal node on level l ranging from t down to 1, newval(x) is set to a value v (this is a value equal to or ⊥ for levels greater or equal than 2, and for level 1 it is either a proposed value or ⊥ if no valid value is received) if there are (n -t -l) children of x the new values of which are set to and among them there is a strict majority with the variable cval set to v. More formally: (i) Let T = {y | y child of x ∧ newval(y) = }.

(ii) newval(x) ← v if a strict majority of the cval of the children of x that belong to T are set to a same value v.

• When x = λ, newval(x) ← v if a strict majority of the new values of its children (these are either proposed values or the default value ⊥ if no valid value has been computed) are set to a same non-⊥ value v; otherwise it is set to a default value v 0 .

The intuition that is behind the values val(x), cval(x) and newval(x) of a node x of a given level l is the following. For the nodes of level 1 and level 2, val(x) is a proposed value as in the original EIG protocol. For the other levels l, 1 < l ≤ t, let us consider that x = yjk. val(x) is set to if p k reported that it does not suspect p j . cval(x) is the echo received from p k of the value val(yj) (if both p j and k are correct cval(x) = val(yj)).

The values newval are a correction of val during the execution of the decision making procedure according to what the child nodes of x reported as an echo of val(x). newval(x) is the information whether p i considers that p k suspects p j or not. val(x) is the suspicion information reported by p k and newval(x) is the information "computed" by p i (using the echoes and the suspicion information of the lower levels) on whether p k suspects p j or not. Then the values newval of this level are used as a mask to re-apply the confirmation mechanism. Only the echoes cval(xjk) of the processes p k that do not suspect process p y (newval(xjk) evaluated to ) are considered for the confirmation mechanism of the value val(xj) of node xj (xj is the parent node of node xjk). For a node x of level 1, newval(x) does not contain an information about suspicions as there is only one process id in the label x; it is indeed the corrected value of the original value received by p i from p j .

Let us note that whereas in the original EIG protocol only the values associated to the leaves of the tree are used to compute the decision value, i.e., newval(x) for each non-leaf node is a function of the new values assigned to its child nodes, in our protocol the value newval(x) depends on both newval and cval values associated with its child nodes.

Correctness Proof

The correctness proof is tailored along the analysis of the (original) EIG protocol as proposed by Bar-Noy et al. [START_REF] Bar-Noy | Shifting Gears: Changing Algorithms on the Fly To Expedite Byzantine Agreement[END_REF] and described in the book by Lynch [START_REF] Lynch | Distributed Algorithms[END_REF]. Although the steps of both analysis are similar, due to the use of the concept of EIG trees, the proofs often rely on different argumentsmore subtle in case of our protocol, as it uses only a small amount of exchanged information. The proof of termination is obvious, therefore in the remainder we focus on validity and agreement.

Lemma 1 Each message sent by a correct process at round r is confirmed by at least all correct processes at round r + 1. Said otherwise, a correct process p i never suspects a correct process p j and thus always relays correctly the messages of p j .

Proof of Lemma 1: The confirmation mechanism says that an information sent by a process p j in the main part of a message is confirmed if it is echoed by at least (n -t) different processes; otherwise, the sender is necessarily Byzantine (assuming t < n/3). If a correct process p i sends a message at some round r, it will send the very same message m to all processes and at least all correct processes (n -t processes) will echo the main part of m to all processes at round r + 1. Consequently at the end of round r + 1 all correct processes will receive at least n -t echos related to message m broadcast at round r by p i .

Notation: As each process maintains its own EIG tree structure, there are n nodes labeled x, one for each process of the system. Thus, val(x) i is used to refer to the value that is associated with the node labeled x of the EIG tree maintained by process p i .

Lemma 2 After t + 1 rounds of the proposed protocol, the following holds. If p i , p j and p k are correct processes, with i = j, then val(x) i = val(x) j for every label x ending in k. Similarly, cval(x) i = cval(x) j if x belongs to a level greater than 1 (otherwise, it is not set).

Proof of Lemma 2: The proof of this lemma follows directly from the fact that a correct process sends the same messages to all processes including itself, and that val(x) i and cval(x) i are either proposed values or suspicion information reported to p i by p k .

Lemma 3 extends the previous one to new values.

Lemma 3 After t + 1 rounds of the proposed protocol, the following holds. Suppose that x is a label ending with the index of a correct process. Then there is a value v such that val(x) i = newval(x) i = v for all correct processes p i .

Proof of Lemma 3:

The proof is by induction on the length of the tree labels from t + 1 down to 1.

Base case: the leaves x of the tree (of length t + 1). From Lemma 2, val(x) i is the same (call this value v) for all correct processes p i . And by definition of new values, newval(x) i = val(x) i for all correct processes p i .

Induction: Let us consider a label x of length , 1 ≤ ≤ t ending with the index of a correct process p j (x = yj). By Lemma 2 all correct processes p i have the same val(x) i (call it v). By the proposed algorithm, for any node labeled xk (k being the id of a correct process), cval(xk) i = val(x) i = v as cval(xk) i is the echo of val(x) i sent by process p k .

Moreover, by Lemma 1, no correct process suspects a correct process. Consequently, for any node labeled xk (k being the id of a correct process), val(xk) i = . By the induction hypothesis, newval(xk) i = . Let us now show that a strict majority of the children of node x are correct processes. Indeed, x has n -children. As there are at most t Byzantine processes, we are sure that at least (n -t -l) child nodes xk of x end with the id k of a correct process. As ≤ t we have (n -t -l) ≥ (n -2t) > t because n > 3t. To sum up, for all child nodes xk of x (p k being a correct process), we have newval(xk) i = and cval(xk) i = val(x) i and these child processes are a strict majority. Consequently, by the decision making procedure of the proposed algorithm, newval(x) i is set to val(x) i proving the lemma. (Although for = 1 or 2, the values of val and cval are proposed values, the same reasoning holds.) Theorem 1 (Validity) If all correct processes begin with the same initial value v, then the only possible decision value for correct processes is v.

Proof of Theorem 1: If all correct processes propose the same value v, then val(j) i = v for any pair p i , p j of correct processes. By Lemma 3 newval(j) i = v for any pair p i , p j of correct processes. The majority rule used by the decision procedure implies that newval(λ) i = v for all correct processes p i .

In order to prove the agreement property of the protocol, we reuse the definition of path covering set similarly to the EIG protocol. A subset C of the nodes of an EIG tree is a path covering if every path from the root to a leaf of the tree contains at least one node in C. Moreover a node x is said to be common for a given execution of the protocol (recall that each process has its own version of the tree) if newval(x) i is the same for all correct processes p i . A given path covering is said to be common for an execution if all of its nodes are common in that execution.

The proof of the next Lemma is exactly the same as for the original EIG protocol, however we include it here for completeness.

Lemma 4 ([17]) After t + 1 rounds of the proposed protocol, there exists a path covering that is common in this execution.

Proof of Lemma 4: We prove that the set C of all the nodes whose labels are of the form xi where p i is a correct process is a common path covering. First, by Lemma 3 all these nodes are common as they end with a correct process id. Second, as each path from the root to a leaf has exactly t + 1 non-root nodes and no process id appears more than once, consequently there is at least one node whose label ends with the id of a correct process since there are at most t Byzantine processes.

Lemma 5 After t + 1 rounds of the proposed protocol, the following holds. If there is a common path covering of the sub-tree rooted at a node labeled x, then either x is common or one of its ancestors is common.

Proof of Lemma 5:

The proof is by induction on the length of the tree labels from t + 1 down to 1.

Base case: The leaves x of the tree (of length t+1). The only node of the common path covering is x itself, which is common by definition of a common path covering.

Induction: Assume the lemma is true for labels greater then l, where 0 ≤ l ≤ t, if any. Let x be a node label of size l and C a common path covering rooted at x. If x ∈ C or if x ends with the id of a correct process then the lemma holds by, respectively, the definition of C and Lemma 3. If x has a correct ancestor then the lemma also holds. So let us consider the case where x is composed of the ids of Byzantine processes. By the definition of a common path covering, any child x of x is a common path covering and, moreover, by the induction hypothesis, is common. According to the decision making procedure (the computing of newval(x)), there are three cases to consider:

• x belongs to level l = t. As the process ids that compose a node x of level l = t are all Byzantine (see above), consequently all its child nodes end with the id j of correct processes and these nodes are common by the induction hypothesis. On the other side, for each child node xj, cval(xj) is a value reported by a correct process p j . By Lemma 1, correct processes report correctly messages and thus, as the decision making procedure is deterministic and correct processes have the same data concerning x, all correct processes will compute the same newval(x) and x is common.

• x belongs to level l ≤ t -1. Suppose x = yj, for some node y and process p j . Let us consider the set of process ids top set = {k | xk is a child node of x ∧ newval(xk) = }. This set contains process ids k such that the child node of x the label of which terminates with the id k has a newval set to . This set is the same for all the EIG trees maintained by the different correct processes by the induction hypothesis. If | top set |< (n -t -l) then by the decision making procedure, any correct process p i sets newval(x) to the same value ⊥ and the lemma follows.

If | top set |≥ (n -t -l) then at least (n -t -l) -(t -l) = n -2t > t + 1 of the processes represented in top set are correct (recall that the number of Byzantine processes whose ids are in top set is at most t -l as x is composed of the ids of l Byzantine processes). This means that among the processes represented in the set top set there is a strict majority of correct processes. Moreover, this majority of such correct processes p k do not suspect process p j (recall that x = yj) by the definition of the set top set and by Lemma 3 applied to node xk. If they do not suspect p j this means that they reported the same value cval(xk). Indeed, if two correct processes report different values from some process, it is necessary that at most one of these processes can confirm the value it reported and the second one will suspect the sender (by the confirmation mechanism). Hence, the value cval(xk) is a strict majority among the processes of top set, and consequently this same value is assigned to newval(x) and x is common.

• x = λ (level l = 0). By the definition of newval(x) and the induction hypothesis, x is common. In more details, suppose to the contrary that λ is not common. Then, by inductive hypothesis, each of its children y consisting of a unique process id would be common, which means that it has the same newval(y) k across correct processes p k . Consequently, by the definition of newval(λ) and by the fact that the number of children of λ consisting of a correct process id is at least n -t > t, the newval(λ) i are the same across correct processes p i . This means that λ is common, violating our contradictory assumption.

Theorem 2 (Agreement) The proposed protocol ensures the agreement property of consensus.

Proof of Theorem 2: After t + 1 rounds of the algorithm, by lemmas 4 and 5 and the fact that the node λ has no ancestor, λ is common. Agreement follows as newval(λ) is the decision value.

Complexity Analysis and Improvement

If we consider binary consensus (only two possible value can be proposed), the main algorithm, as described in Section 4, achieves O(n 3 ) communication complexity, in terms of the number of bits sent by any correct process. Each process sends, respectively, O(1), O(n) and O(n 2 ) bits during the first three rounds, and then O(n 2 ) bits in each subsequent round: a list of suspected processes and the echoes of the lists received in the previous round (n 2 bits at most). For the maximal value of t (which is O(n)), the communication bit complexity of this protocol is O(n 3 ) per process, and thus O(n 4 ) for all correct processes in total.

In the case of multivalued consensus, the proposed value of each process is taken from a set V of proposable values, the size of which is k. The bit complexity of the first three rounds becomes O(n 2 ) log 2 k per process, where the factor log 2 k comes from the size of the binary representation of a proposed value. The complexity of the subsequent rounds of the algorithm does not depend on k, as processes only exchange suspicion information, namely, O(n 3 ) bits per process. The total bit complexity is thus O(max(n 4 , n 3 log k)). If log 2 k = O(n), the bit complexity of the algorithm is O(n 4 ).

However, similarly to the floodset protocol for solving the consensus problem in crash-prone synchronous systems, our protocol can be modified to use only an incremental dissemination of the suspicions (instead of sending the whole list of suspected processes all the time). Indeed, once a process suspects another process it will suspect it until the end of the execution and there is no need to resend this information at each round. Namely, each suspicion is sent only once, that is, in the first time where it is discovered. A correct process can suspect at most t processes. Obviously, if a suspicion is sent only once, the echo is also sent only once by correct processes. A Byzantine process can be suspected by possibly all the other processes. Due to the relay, we can say that during the execution of the protocol each process sends t suspicions and relays (n -1)t suspicions. Each relay of a suspicion needs two process ids, i.e., who suspects who. That is, the protocol needs O(nt log n) bits per process, where the factor log 2 n comes from the size of the binary representation of a process id. Moreover, each process sends respectively O(1), O(n) and O(n 2 ) bits during the first three rounds, which are special rounds. Finally, the property of well-formed messages requires from each process to send its id, of logarithmic size, to each process in every round; this contributes another O(t log n) to the bit communication complexity per each process. For the maximal value of t, which is O(n), the bit communication complexity of the modified protocol is O(n 2 log n) per process, therefore O(n 3 log n) in total for binary consensus.

Again, if we consider that the proposed values are taken from a set V of size k then the complexity of the algorithm becomes O(n 3 log(max(n, k))).

Figure 1 :

 1 Figure 1: An EIG tree

  The values received by process p i are used to decorate the nodes of level 1 of the EIG tree maintained by p i . As explained above, if p i has not received a message, or received a non well-formed message from a given process p x , it decorates the node labeled x with the value ⊥, i.e., val(x) ← ⊥. If it received a proposable value v, it sets val(x) to v. The variable cval(x) is not used for nodes x on level 1.Round 2. Each process p i sends an empty main part and echoes the messages (i.e., initial values) it received in the first round. Thus, each message is a sequence of up to n initial values. The values received by p i (up to n(n -1) values) are used to decorate the nodes of level 2 of the EIG tree maintained by p

i . Node x = jk is decorated by the value v, i.e., cval(x) ← v, if p k reports that it received v from p j at level 1; cval(x) is set to ⊥ if no valid value is reported.

This suggests that the bit complexity of the algorithm is O(n 4 ), as each of the n processes sends up to n

bits during each of the t < n/3 rounds of the algorithm; however we will show later in Section 6 that this amount of information can be reduced to O(n

log n).

Sometimes an EIG tree was presented as a collection of n trees, each of t + 1 levels ranging from 1 to t + 1; these trees correspond to the n subtrees of our single EIG tree, each rooted in a distinct node at level 1. Both these approaches are equivalent.

Acknowledgments

We would like to thank Nancy Lynch for suggesting this research direction when Achour Mostefaoui spent three months visiting her group. We are also thankful to Yoram Moses for all the discussions and valuable remarks. Finally we would like to thank the anonymous reviewers whose comments helped to improve this paper.