Question 5 – EIG Trees
Consider an EIG tree, for N participants, at most F of which faulty, and L messaging rounds. A node is called distinguished if its label ends in a non-faulty participant number.
(a) Draw a tree diagram and highlight all distinguished nodes, for the case when N=4 and participant #1 is faulty.
(b) For an arbitrary N, assuming that L>F, prove that any root-to-leaves path passes through at least one distinguished node.
(c) For an arbitrary N, assuming that N>3F, prove that, at each level, any sibling group contains a majority of distinguished nodes.
(d) For an arbitrary N, prove that both conditions (b) and (c) are achieved when N >= 3F +1.
