Exponential Information Gathering (EIG) Algorithm for Byzantine Agreement

Reaching consensus is one of the most fundamental challenges in distributed systems. Consider a distributed database cluster where Node A reports an item price of $1,000 while Node B reports$2,000. If clients receive divergent values depending on which replica handles the query, data consistency breaks down. To present a unified, coherent state, nodes must communicate and agree on a single source of truth.

In standard crash-fault-tolerant (CFT) consensus models (such as Raft or Paxos), we assume nodes may crash, restart, or experience network latency, but they remain honest—they never intentionally fabricate or tamper with messages. In adversarial environments, however, nodes may be Byzantine (malicious, compromised, or faulty), actively attempting to corrupt system sanity by sending contradictory or garbage values to different peers.

The Exponential Information Gathering (EIG) algorithm is a foundational distributed consensus algorithm designed to achieve Byzantine Agreement. By systematically propagating and organizing values across multiple communication rounds into an exponential tree structure, EIG allows non-faulty nodes to reach identical, correct consensus even when faced with arbitrary Byzantine failures.

---

The Byzantine Agreement Problem

In a network of $n$ processes where up to $f$ processes may be Byzantine:

1. Agreement: All non-faulty (honest) processes must decide on the exact same value.
2. Validity: If all honest processes start with the same initial value $v$, every honest process must decide $v$.
3. Termination: Every honest process must eventually decide upon a value.

Unlike crash failures, a Byzantine node can:

• Lie about its initial state.
• Send value $X$ to Node A and value $Y$ to Node B.
• Forge or modify values received from other nodes.
• Go completely silent.

To overcome this, honest nodes must gather enough redundant information about who reported what to whom to isolate and discard conflicting data.

---

Theoretical Bounds and Assumptions

To guarantee Byzantine agreement in a synchronous network without cryptographic signatures, the EIG algorithm relies on two mathematical constraints:

1. Node Bound ($n > 3f$): The total number of nodes $n$ must be strictly greater than three times the number of faulty nodes $f$. $$n \ge 3f + 1$$ For example, to tolerate $f = 1$ malicious node, the network requires at least $n = 4$ nodes.
2. Round Complexity ($f + 1$ Rounds): The protocol must execute for at least $f + 1$ synchronous communication rounds to ensure that honest nodes gather sufficient disjoint paths of communication.

---

The EIG Tree Data Structure

Rather than maintaining a single shared or centralized state, each node independently constructs its own local EIG tree.

An EIG tree represents message transmission histories along permutation paths:

• Root Node: Labeled with the empty string $\lambda$ (representing the system-wide perspective).
• Level 1 Nodes: Labeled with individual node IDs ($A, B, C, \dots$). Node $A$‘s child at Level 1 stores what $A$ claimed its initial value was.
• Level $k$ Nodes: Labeled with strings of length $k$ representing distinct permutation sequences without repeated node IDs (e.g., node path $ABC$ represents: ”$C$ told $B$ that $A$ told $C$ value $V$ ”).
• Depth: The tree is constructed up to level $f + 1$.

                    [ λ ] (Root)
                   /  |  \
                 /    |    \
               /      |      \
             [A]     [B]     [C]
            /   \   /   \   /   \
          [AB] [AC][BA] [BC][CA] [CB]
          /     |    |   |    |    \
       [ABC]  [ACB][BAC][BCA][CAB][CBA]

At each level $k$, the tree enumerates all permutations of node subsets of length $k$. As the tree depth increases, the number of nodes at each level grows factorially/exponentially, which is why the approach is called Exponential Information Gathering.

---

Step-by-Step Algorithm Walkthrough

The EIG algorithm operates in two primary phases: the Information Gathering Phase (top-down / level-by-level broadcast) and the Decision Phase (bottom-up majority resolution).

flowchart TD
    A[Start: Initial Local Values] --> B[Round 1: Broadcast Local Value to All Peers]
    B --> C[Round k to f+1: Broadcast Level k-1 Labels]
    C --> D[Sanity Checks: Discard Garbage / Out-of-Bounds Values]
    D --> E[Complete EIG Tree Built locally]
    E --> F[Decision Phase: Bottom-Up Post-Order Traversal]
    F --> G[Non-Leaf: Resolve Majority of Children]
    G --> H{Strict Majority Exists?}
    H -- Yes --> I[Assign Majority Value to Parent Node]
    H -- No --> J[Assign Default Fallback Value v_default]
    I --> K[Repeat until Root λ is Resolved]
    J --> K
    K --> L[Consensus Achieved: Value at Root]

Phase 1: Information Gathering ($f + 1$ Rounds)

1. Round 1: Every node broadcasts its initial proposed value to all other nodes. Upon receiving a message from node $p$, the local node places that value into node $[p]$ at Level 1 of its local EIG tree.

2. Rounds $2$ through $f + 1$: In round $k$, each node broadcasts the values it stored at level $k - 1$ in the previous round, appending its own ID to the path label.

   • If node $B$ receives a value from node $C$ claiming that node $A$‘s value was $v$, node $B$ stores $v$ at path $[AC]$ in its local EIG tree.
   • A node only relays paths that do not already include the recipient or itself, maintaining strictly non-repeating node labels.

3. Syntactic and Semantic Sanity Checks: Malicious nodes may attempt to inject malformed data or out-of-range types. Before recording an incoming value into the tree:

   • Type checking: If the expected data is an integer, non-integer inputs are discarded.
   • Range validation: If values must fall within $[0, 100]$ and a node receives $5,000$, the payload is identified as corrupted and recorded as null (or a known empty marker).

---

Phase 2: Decision Making (Bottom-Up Majority Resolution)

Once $f + 1$ rounds are complete, each honest node possesses a populated EIG tree. To filter out Byzantine lies, each node evaluates its local tree from the leaves upward to the root (similar to a post-order traversal):

1. Leaf Nodes (Level $f + 1$): The resolved value for any leaf node is simply the raw value stored in that node.

2. Internal Nodes (Level $k < f + 1$): The resolved value $\text{val}(u)$ for an internal node $u$ is computed as the strict majority of the resolved values of its direct children:

   $$\text{val}(u) = \text{majority}\left(\{\text{val}(c) \mid c \in \text{children}(u)\}\right)$$
   • Strict Majority: If more than half of the immediate child nodes resolve to the same value $v$, then $\text{val}(u) = v$.
   • No Majority (Tie / Split): If there is no strict majority (e.g., children resolve to conflicting values in equal measure, or too many null values exist), the node defaults to a predefined fallback value $v_{\text{default}}$.

3. Root Resolution: The procedure recurses up to the root node $\lambda$. The resolved value at $\lambda$ represents the final decision of that process.

Because all non-faulty nodes follow the deterministic evaluation rules over trees constructed from $n > 3f$ connectivity, the resolved value at the root is guaranteed to be identical across all honest nodes.

---

Why EIG Neutralizes Byzantine Nodes

The robustness of EIG stems from combinatorial path explosion. Consider an adversarial node $M$ attempting to split the network by telling Node A that its value is $1$ and Node B that its value is $2$.

• In subsequent rounds, honest nodes propagate what they heard from $M$ across independent paths ($MA, MB, MC, \dots$).
• Because honest nodes dominate the system ($n > 3f$), the overwhelming majority of paths passing through the network originate from and are relayed by honest processes.
• A Byzantine process can only corrupt paths where it or fellow corrupt nodes reside.
• When non-faulty nodes resolve values from the bottom up, any localized discrepancies or lies injected by $M$ are diluted and outvoted by honest peer paths during the majority calculation.

Consequently, the corrupted values are absorbed at lower levels of the tree and never propagate to the root.

---

Complexity and Practical Trade-offs

While EIG provides an elegant mathematical foundation for proving Byzantine agreement, it has significant operational trade-offs:

Metric	Complexity	Implication
Rounds	$f + 1$	Optimal round complexity for deterministic Byzantine consensus without cryptography.
Message Complexity	$O(n^{f+1})$	Number of messages grows factorially/exponentially with the number of allowed faults.
Space Complexity	$O(n^{f+1})$	Local EIG tree size per node scales exponentially with $f$.

Because storing and transmitting $O(n^{f+1})$ values becomes prohibitively expensive for large networks or large values of $f$, raw EIG is rarely used directly in high-throughput production systems. Instead, modern Byzantine Fault Tolerant (BFT) protocols—such as PBFT (Practical Byzantine Fault Tolerance), Tendermint, and HotStuff—achieve consensus using digital signatures, leader-based proposals, and multi-phase commit rounds ($O(n^2)$ message complexity) rather than exhaustive exponential state gathering.

Nonetheless, EIG remains the gold standard in distributed computing theory for establishing lower bounds and understanding the fundamental information requirements necessary to defeat arbitrary, malicious actors.