Exponential Information Gathering (EIG): Crash-Tolerant Distributed Consensus

Introduction to Distributed Consensus and Crash Faults

Reaching consensus is one of the foundational challenges in distributed systems. Consider a replicated database cluster where one node records an item price as $1,000 while another node records it as $2,000. Depending on which replica serves a client request, clients observe conflicting states, leading to severe data inconsistency.

To prevent divergence, distributed nodes must exchange messages, reconcile differing views, and agree on a singular, definitive value. The complexity of this task depends heavily on the failure model:

1. Ideal Network & Crash-Free Processes: When messages never drop and nodes never crash, achieving consensus is trivial.
2. Unreliable Networks: In purely asynchronous systems with unpredictable message drops or unbounded delays, consensus cannot be guaranteed deterministically (as established by the FLP Impossibility result).
3. Reliable Network with Crash-Prone Nodes: If the network is synchronous and reliable (messages sent between non-faulty nodes are guaranteed to be delivered within bounded time), but individual nodes can crash unexpectedly, consensus is achievable.

One canonical, mathematically rigorous approach for this scenario is the Exponential Information Gathering (EIG) algorithm. While computationally and structurally expensive, EIG provides strong theoretical guarantees against up to $f$ crash failures and establishes the architectural baseline for Byzantine Fault Tolerant (BFT) protocols.

---

The Core Premise of EIG

The central mechanism of EIG relies on exhaustive path tracking:

• Nodes relay not only their own value but also every sequence of values they have heard from other nodes.
• Each node tracks the full historical path of how a message traversed the network.
• Message exchange proceeds over a fixed number of rounds determined by the maximum allowable crash faults ($f$).
• At the conclusion of these rounds, all non-faulty nodes possess an identical internal state representation (an identical EIG tree) and can independently execute a deterministic decision function.

---

The EIG Tree Data Structure

The EIG algorithm models information exchange as a specialized tree that expands level by level, encoding every valid permutation of node message paths without internal cycles.

Structural Properties

Let $n$ be the total number of processes/nodes in the network.

• Root Node: Denoted by the empty string $\epsilon$ at Level $0$.
• Level 1: Contains children corresponding to each process in the cluster: $[a, b, c]$. Each node tracks the value reported by that specific process.
• Level $k$ Branching Factor: At any level $k$, each node has exactly $(n - k)$ children.
• Path Uniqueness: A path from the root down to level $k$ represents an ordered sequence of nodes through which the message was forwarded (e.g., path $a \to b \to c$). Cycles are explicitly disallowed (no process appears more than once along any path from the root).
• Leaves: When expanded fully, the leaf nodes represent all possible non-repeating permutations of processes.

graph TD
    Root["Root (ε)"] --> A["A"]
    Root --> B["B"]
    Root --> C["C"]

    A --> AB["A-B"]
    A --> AC["A-C"]

    B --> BA["B-A"]
    B --> BC["B-C"]

    C --> CA["C-A"]
    C --> CB["C-B"]

    AB --> ABC["A-B-C"]
    AC --> ACB["A-C-B"]
    BA --> BAC["B-A-C"]
    BC --> BCA["B-C-A"]
    CA --> CAB["C-A-B"]
    CB --> CBA["C-B-A"]

For a cluster of size $n = 3$:

• Level 0: Root (1 node)
• Level 1: $n = 3$ nodes ($A, B, C$)
• Level 2: Each node has $n - 1 = 2$ children ($AB, AC, BA, BC, CA, CB$)
• Level 3: Each node has $n - 2 = 1$ child ($ABC, ACB, BAC, BCA, CAB, CBA$)

---

The Algorithm: $f + 1$ Rounds of Gathering

If the system is designed to tolerate up to $f$ node crashes, the algorithm runs for exactly $f + 1$ rounds. The $(f + 1)$-th round guarantees that even if $f$ nodes crash sequentially—one per round—there is at least one round in which all active processes successfully broadcast, ensuring every surviving node constructs an identical tree.

Each round constructs the corresponding level in the local EIG tree.

sequenceDiagram
    autonumber
    participant NodeA as Node A
    participant NodeB as Node B
    participant NodeC as Node C

    Note over NodeA, NodeC: Round 1 (Construct Level 1)
    NodeA->>NodeB: Broadcast v_A
    NodeA->>NodeC: Broadcast v_A
    NodeB->>NodeA: Broadcast v_B
    NodeB->>NodeC: Broadcast v_B
    NodeC->>NodeA: Broadcast v_C
    NodeC->>NodeB: Broadcast v_C
    Note over NodeA, NodeC: Round 2 (Construct Level 2)
    NodeA->>NodeB: Forward pairs (B, v_B), (C, v_C) excluding recipient
    NodeB->>NodeA: Forward pairs (A, v_A), (C, v_C) excluding recipient
    NodeC->>NodeA: Forward pairs (A, v_A), (B, v_B) excluding recipient

Round 1: Local Value Exchange

1. Every process $i$ broadcasts its initial proposed value $v_i$ to every other process in the network (including itself).
2. When process $i$ receives value $v_j$ from process $j$, it updates its tree at label $j$: $\text{Tree}[j] = v_j$
3. At the end of Round 1, Level 1 of the EIG tree is populated across all surviving nodes.

Rounds 2 Through $f + 1$: Path Propagation

For any round $k$ ($2 \le k \le f + 1$):

1. Every process $i$ inspects Level $k-1$ of its tree.
2. Process $i$ sends all pairs $(x, \text{Tree}[x])$ from Level $k-1$ to all other processes, provided that process $i$ does not already appear in path $x$.
3. When process $j$ receives a message with path label $x$ and value $v$ from process $i$, process $j$ records the value at the child node representing path $x \cdot i$: $\text{Tree}[x \cdot i] = v$
4. Because processes forward information without repeating identifiers in the path label, cyclic gossip is prevented, and paths strictly mirror transmission histories.

By the end of $f + 1$ rounds, regardless of which $f$ processes crashed along the way, the surviving nodes possess structurally identical subtrees for all communicating components.

---

The Decision Phase

Once information gathering concludes at round $f + 1$, nodes transition to making an autonomous decision. No further network communication is permitted; consensus must be reached locally.

Because every non-faulty node has gathered information identically, applying a deterministic reduction function across the tree yields the exact same output on all nodes.

Strategy 1: The Singleton Rule

1. Traverse all populated nodes within the EIG tree.
2. Collect all observed values into a set $S$.
3. Evaluation:
   • If $|S| = 1$ (the set is a singleton $\{v\}$), decide on value $v$.
   • If $|S| > 1$ (conflicting proposals were observed), fall back to a predefined default safe state $v_0$ (equivalent to a transaction abort or rollback).

$\text{Decision}(S) = \begin{cases} v & \text{if } S = \{v\} \\ v_0 & \text{if } |S| > 1 \text{ or } S = \emptyset \end{cases}$

Strategy 2: Total Ordering Reduction

If the application domain defines a strict total order over values (e.g., sequence numbers, logical timestamps, or monotonic numerical ordering):

• Nodes independently apply a deterministic reduction (such as $\max(S)$, $\min(S)$, or newest by timestamp).
• Because every node executes the exact same deterministic function over the exact same set $S$, all nodes reach an identical consensus without needing to abort to $v_0$.

---

Why Study an Exponential Algorithm?

In practical modern engineering, algorithms like Raft, Multi-Paxos, or Viewstamped Replication are preferred because they avoid the combinatorial explosion of EIG. However, EIG remains foundational in distributed systems theory for two reasons:

1. Theoretical Lower Bounds: EIG proves that consensus under crash failures can be solved deterministically in synchronous systems within $f + 1$ rounds. It sets the baseline for the minimum number of rounds required when crash failures occur.
2. Bridge to Byzantine Fault Tolerance: EIG forms the direct intellectual foundation for solving the Byzantine Generals Problem (Lamport, Shostak, Pease). When nodes are not merely crashing but actively adversarial (sending conflicting messages to different peers), gathering permutations of message paths allows honest nodes to cross-reference claims, filter corrupt data via recursive majority voting, and isolate malicious actors.