An exponential protocol

Each process will have a huge tree as its data structure. Let t denote, as usual, the number of traitors. The tree will have t+2 levels, numbered from (the root) to t+1. The nodes in the tree will be labeled $\pi=p_{i_1}p_{i_2}\cdots p_{i_k}$, where the p_is denote different generals (processes), i.e. $p_i\ne p_j$ for all $p_i,p_j \in \pi$ . The basic idea of the protocol is to transmit one own's value, echo the values so received, echo the echoes, and so on. The relation

$$\content(p_{i_1}p_{i_2}\cdots p_{i_k})=x$$ (1)

should be interpreted as ``p_ik told me that p_i<<532>>k-1 told him that $\ldots$ p_i2 told him that p_i1 told him that his initial value was x''. The value x will be stored in the tree node with label $p_{i_1}p_{i_2}\cdots p_{i_k}$.

 

Figure 3.1: Each process has a huge tree as its data structure. On level k in the tree, the degree of each internal node is n-k. There are t+2 levels in the tree, where t is the number of traitors. This means that every internal node will have at least 2t+1 children.

We now describe the protocol. The protocol is in two phases. During the first phase, processes shuffle messages around and fill in the tree. The second phase is used to evaluate a function of the information stored in the tree. No messages are sent during this second phase.

The first phase takes t+1 communication rounds and is as follows. In round , every process will send its input value to everybody. Each process fills its first level according to the messages it receives. In round i>0 every process sends its ith level to everybody else. If p_j receives a message from p_i saying ``The content of node $\pi$ in my tree is x'' it puts x into node $\pi p_i$.

The second phase starts at the end of round t+1. Each process p_i starts an evaluation procedure on its tree T_i. We denote the content of node $\pi$ in T_i by $\tree_i(\pi)$ and define the function $\resolve_i$ as follows:  

$$\resolve_i(\pi)=\begin{cases} \tree_i(\pi) & \mbox{if $\pi... ...f} \ \perp & \mbox{if the majority is undefined} \end{cases}$$ (2)

Definition 11952

We say that $\pi$ is trustworthy if $\pi=\pi'p$, where p is loyal.

Lemma 11958

Let $\pi=\pi'p$ be trustworthy and let $x=\tree_p(\pi')$.Then, for all $i,j,q,r \in L$, 

$$\tree_i(\pi q) = \tree_j(\pi q) = x$$ (3)

and  

$$\tree_i(\pi q) = \tree_i(\pi r) = x.$$ (4)

Proof. By definition of trustworthy, $p \in L$.By the algorithm, p will send x to everybody, including $q \in L$. Since q is also loyal, $\tree_q(\pi'p)=\tree_q(\pi)=x$.Then, q will send the content of its node $\pi$ to all. If $i,j \in L$ then $\tree_i(\pi q)=\tree_j(\pi q)=x$.A similar argument proves the other claim.$\Box$

The above lemma says that if $\pi$ is trustworthy then all children of $\pi$ corresponding to a loyal process will store the same value. Since the degree of every node is at least 2t+1, this ensures a majority among the values stored at the children of a trustworthy node.

Definition 11975

We say that $\pi$ is nice if

$$\forall i,j\in L \; \resolve_i(\pi)=\resolve_j(\pi).$$ (5)

Lemma 11979

Let $\pi=\pi'p$ be trustworthy. Then

1.

$\pi$ is nice,

2.

$\forall i\in L \; \resolve_i(\pi)=\tree_i(\pi)$.

Proof. We will use induction. If $\pi$ is a leaf, then by Equation 3.2

$$\forall i\in L \; \resolve_i(\pi)=\tree_i(\pi).$$ (6)

Furthermore, by the definition of the protocol, $\tree_i(\pi)=\tree_p(\pi')$, and since p is loyal, this implies that

$$\forall i,j\in L \; \resolve_i(\pi)=\resolve_j(\pi).$$ (7)

This concludes the base case.

For the inductive step, let $x := \tree_p(\pi')$ and let i be any process in L. By the algorithm, $x=\tree_p(\pi')=\tree_i(\pi' p)=\tree_i(\pi)$.We first show that $\tree_i(\pi)=\resolve_i(\pi)$.By Equation 3.4,

$$\tree_i(\pi q) = \tree_i(\pi r) = x$$

for all $q,r \in L$. By the induction hypothesis

$$\resolve_i(\pi q) = \tree_i(\pi q)$$

for all $q \in L$.This implies

$$x = \maj_{q \not \in \pi} \{\resolve_i(\pi q)\}$$

since $\pi$ has at least 2t+1 children.

We now show that $\resolve_i(\pi)=\resolve_j(\pi)$ for all loyal i and j. By Equation 3.3, for all loyal q

$$\tree_i(\pi q) = \tree_j(\pi q) = x$$

which implies

$$x = \maj_{q \not \in \pi} \{\resolve_j(\pi q)\}$$

$\Box$

The above lemma already implies non-triviality, since the root of the tree has at least n-t>t trustworthy children. Limited bureaucracy, of course, follows from the protocol definition. We now establish agreement by showing that the root too is nice.

Definition 12007

We say that $\pi$ has a nice frontier if, along every path from $\pi$ to a leaf, there is a nice vertex.

Notice that the root has a nice frontier, since every path from a leaf to the root has length t+1 and one of the nodes along it must be trustworthy.

Lemma 12011

If $\pi$ has a nice frontier, then $\pi$ is nice.

Proof. Again by induction. If $\pi$ is a leaf the proof is trivial. Now suppose that $\pi$ is not a leaf. If $\pi$ is nice we are done. Otherwise all children of $\pi$ are nice, by the induction hypothesis. This, however, implies that $\pi$ is nice.$\Box$

By this last lemma we also have agreement, which concludes the proof.