EIG tree $T_{n,f}$ for $n$ processes, $f$ failures.

• $f + 2$ levels
• Each node has a label $x$

算法

• 每个进程都有一个EIG树
• Initial: decorate root(labelled by $\lambda$, the empty string) with $i$'s input value $v_i$, i.e. $val(\lambda) = v_i$
• Decorate the node $x$ of its tree with some values $val(x)$, level by level
• Round $r\geq 1$
  • send all pairs $(x,val(x))$ for level $r-1$ to everyone
  • when receive $(x,val(x))$ from process $j$, decorate the node $xj$ with the $val(x)$
  • if no msg from $j$, decorate $xj$ with $\bot$
• The decoration for $i_1i_2i_3...i_k$ in p'th tree is the value $v$ such that ($i_k$ told p) that ($i_{k-1}$ told $i_k$) that ... that($i_1$ told $i_2$) that $i_1$'s initial value is $v$
• Decision:
  • $W$: set of all value in the tree
  • if $|W|=1$ decide that value, else default $v_0$

Illusion of EIG for Stopping Failure

Illusion of EIG for Stopping Failure

Complexity

• time: $f+1$ rounds
• total number of msg: $\leq (f+1)n^2$
• total number of bits: $O(n^{f+1}b)$ (number of nodes in a EGT tree)